SAT problem
E512973
The SAT problem is a fundamental NP-complete decision problem in computer science that asks whether there exists an assignment of truth values to variables that makes a given Boolean formula evaluate to true.
Statements (54)
| Predicate | Object |
|---|---|
| instanceOf |
Boolean satisfiability problem
ⓘ
NP-complete problem ⓘ computational problem ⓘ decision problem ⓘ |
| abbreviation | SAT ⓘ |
| alsoKnownAs | Boolean satisfiability problem NERFINISHED ⓘ |
| asksWhether | there exists a truth assignment that makes a Boolean formula evaluate to true ⓘ |
| canonicalReference | Cook–Levin theorem NERFINISHED ⓘ |
| certificate | satisfying assignment of variables ⓘ |
| complexityClass | NP ⓘ |
| complexityOf2SAT | solvable in polynomial time ⓘ |
| complexityOf3SAT | NP-complete ⓘ |
| complexityOfHornSAT | solvable in polynomial time ⓘ |
| complexityOfkSATForK≥3 | NP-complete ⓘ |
| field |
computational complexity theory
ⓘ
computer science ⓘ theoretical computer science ⓘ |
| firstNPCompleteProblem | true ⓘ |
| hasAlgorithmicApproach |
CDCL SAT solvers
NERFINISHED
ⓘ
DPLL algorithm NERFINISHED ⓘ backtracking search ⓘ local search SAT solvers ⓘ |
| hasPolynomialTimeAlgorithm | unknown ⓘ |
| input | Boolean formula ⓘ |
| inputRepresentation |
arbitrary Boolean formula over variables and connectives
ⓘ
conjunctive normal form ⓘ disjunctive normal form ⓘ |
| isCompleteFor | class NP under polynomial-time many-one reductions ⓘ |
| isInNP | true ⓘ |
| isNPComplete | true ⓘ |
| isNPHard | true ⓘ |
| logicalConnectives |
AND
ⓘ
NOT ⓘ OR ⓘ |
| NPCompletenessProvedBy | Stephen Cook NERFINISHED ⓘ |
| NPCompletenessProvedIndependentlyBy | Leonid Levin NERFINISHED ⓘ |
| output | YES if the formula is satisfiable, NO otherwise ⓘ |
| relatedOpenProblem | P versus NP problem NERFINISHED ⓘ |
| restriction |
2-SAT
ⓘ
3-SAT ⓘ Horn-SAT ⓘ k-SAT NERFINISHED ⓘ monotone SAT ⓘ planar SAT ⓘ |
| usedFor | reductions in NP-completeness proofs ⓘ |
| usedIn |
artificial intelligence
ⓘ
automated theorem proving ⓘ constraint solving ⓘ hardware verification ⓘ software verification ⓘ |
| valueDomain | truth values true and false ⓘ |
| variableDomain | Boolean variables ⓘ |
| verificationTime | polynomial time given a candidate assignment ⓘ |
| yearNPCompletenessProved | 1971 ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.