Boolean satisfiability problem (SAT)
GPTKB entity
Statements (77)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
theoretical computer science
|
| gptkbp:abbreviation |
gptkb:SAT
|
| gptkbp:complexity |
NP-complete
|
| gptkbp:definedIn |
the problem of determining if there exists an interpretation that satisfies a given Boolean formula
|
| gptkbp:field |
gptkb:complexity_theory
gptkb:logic computer science |
| gptkbp:firstDescribed |
gptkb:Cook-Levin_theorem
|
| gptkbp:firstNPCompleteProblem |
true
|
| gptkbp:generalizes |
gptkb:3-SAT
gptkb:k-SAT |
| gptkbp:hasApplication |
gptkb:machine_learning
gptkb:knowledge_representation combinatorial optimization crypt game theory information retrieval operations research planning robotics semantic web bioinformatics resource allocation formal verification circuit design data mining database theory model checking scheduling automated planning software verification hardware verification VLSI design network design constraint programming logic synthesis security analysis fault diagnosis protocol verification test pattern generation timing analysis ontology reasoning configuration problems knowledge compilation quantified Boolean formula (QBF) solving satisfiability modulo theories (SMT) |
| gptkbp:hasPolynomialTimeAlgorithm |
false
|
| gptkbp:hasSpecialCase |
Boolean satisfiability problem
|
| gptkbp:hasVariant |
gptkb:3-SAT
gptkb:2-SAT gptkb:k-SAT gptkb:MAX-SAT gptkb:QSAT |
| https://www.w3.org/2000/01/rdf-schema#label |
Boolean satisfiability problem (SAT)
|
| gptkbp:input |
Boolean formula
|
| gptkbp:introduced |
gptkb:Stephen_Cook
|
| gptkbp:introducedIn |
1971
|
| gptkbp:output |
satisfiable or unsatisfiable
|
| gptkbp:reduces |
gptkb:Hamiltonian_cycle_problem
gptkb:clique_problem gptkb:vertex_cover_problem integer programming graph coloring problem subset sum problem many other NP-complete problems circuit satisfiability problem |
| gptkbp:relatedTo |
gptkb:P_vs_NP_problem
|
| gptkbp:solvedBy |
gptkb:SAT_solvers
|
| gptkbp:usedIn |
gptkb:artificial_intelligence
automated theorem proving electronic design automation constraint satisfaction |
| gptkbp:bfsParent |
gptkb:NP-hardness
gptkb:NP_(complexity_class) gptkb:NP_(nondeterministic_polynomial_time) gptkb:Quantified_Boolean_Formula_(QBF) |
| gptkbp:bfsLayer |
6
|