|
gptkbp:instanceOf
|
gptkb:theoretical_computer_science
gptkb:Boolean_satisfiability_problem
|
|
gptkbp:closelyRelatedTo
|
gptkb:2-SAT
gptkb:MAX-3SAT
gptkb:k-SAT_for_k_>_3
random 3-SAT
|
|
gptkbp:definedIn
|
satisfiability of Boolean formulas in conjunctive normal form with exactly three literals per clause
|
|
gptkbp:first_proven_NP-complete_by
|
gptkb:Richard_Karp
|
|
gptkbp:hardness_used_for
|
proving inapproximability results
|
|
gptkbp:has_polynomial_time_algorithm_if
|
P = NP
|
|
gptkbp:hasSpecialCase
|
gptkb:k-SAT
|
|
gptkbp:input
|
Boolean formula in 3-CNF
|
|
gptkbp:NP-complete
|
true
|
|
gptkbp:output
|
true if formula is satisfiable, false otherwise
|
|
gptkbp:reduction_from
|
general SAT
|
|
gptkbp:relatedTo
|
gptkb:P_vs_NP_problem
|
|
gptkbp:solvable_by
|
gptkb:DPLL_algorithm
gptkb:CDCL_SAT_solvers
|
|
gptkbp:solvable_in_exponential_time_by
|
brute-force search
|
|
gptkbp:used_in
|
gptkb:theoretical_computer_science
gptkb:artificial_intelligence
gptkb:complexity_theory
cryptography
algorithm design
benchmarking SAT solvers
theory of computational complexity
|
|
gptkbp:year_of_NP-completeness_proof
|
1972
|
|
gptkbp:bfsParent
|
gptkb:NP-completeness
|
|
gptkbp:bfsLayer
|
5
|
|
https://www.w3.org/2000/01/rdf-schema#label
|
3-SAT
|