Statements (22)
Predicate | Object |
---|---|
gptkbp:instanceOf |
theoretical computer science
|
gptkbp:complexity |
NP-complete
|
gptkbp:first_proven_NP-complete_by |
gptkb:Richard_Karp
gptkb:Stephen_Cook |
gptkbp:generalizes |
gptkb:3-SAT
|
gptkbp:has_approximation_algorithms |
yes
|
gptkbp:has_exact_algorithms |
yes
|
gptkbp:has_exponential_time_algorithms |
yes
|
https://www.w3.org/2000/01/rdf-schema#label |
k-SAT for k > 3
|
gptkbp:input |
Boolean formula in conjunctive normal form with k literals per clause
|
gptkbp:is_a_constraint_satisfaction_problem |
yes
|
gptkbp:relatedTo |
gptkb:P_vs_NP_problem
|
gptkbp:solvable_in_polynomial_time_for |
k = 2
|
gptkbp:unsolved_in_polynomial_time_for |
k > 2
|
gptkbp:used_in |
gptkb:artificial_intelligence
cryptography theoretical computer science circuit design theory of computational complexity |
gptkbp:variant |
Boolean satisfiability problem
|
gptkbp:bfsParent |
gptkb:3-SAT
|
gptkbp:bfsLayer |
6
|