SAT
E679891
SAT (the Boolean satisfiability problem) is the fundamental decision problem of determining whether there exists an assignment of truth values that makes a given Boolean formula evaluate to true.
Statements (59)
| Predicate | Object |
|---|---|
| instanceOf |
computational problem
ⓘ
decision problem ⓘ |
| alsoKnownAs |
Boolean satisfiability problem
NERFINISHED
ⓘ
SAT problem ⓘ |
| canonicalForm | conjunctive normal form ⓘ |
| clauseDefinition | disjunction of literals ⓘ |
| commonAlgorithmicApproach |
CDCL (conflict-driven clause learning)
NERFINISHED
ⓘ
DPLL algorithm NERFINISHED ⓘ local search algorithms ⓘ stochastic search ⓘ |
| complexityClass |
NP
ⓘ
NP-complete ⓘ |
| domain | Boolean formulas over variables with values true or false ⓘ |
| field |
computational complexity theory
ⓘ
mathematical logic ⓘ theoretical computer science ⓘ |
| formalDefinition | Given a Boolean formula, determine whether there exists a truth assignment to its variables that makes the formula evaluate to true ⓘ |
| hasImportantVariant |
#SAT
ⓘ
2-SAT NERFINISHED ⓘ 3-SAT NERFINISHED ⓘ Horn-SAT NERFINISHED ⓘ MAX-SAT NERFINISHED ⓘ k-SAT NERFINISHED ⓘ |
| historicalMilestone | first problem proven NP-complete ⓘ |
| importance |
basis for many reductions in complexity theory
ⓘ
central to the theory of NP-completeness ⓘ |
| input | Boolean formula ⓘ |
| isInClassNPBecause | a satisfying assignment can be verified in polynomial time ⓘ |
| isNPCompleteBecause | every problem in NP can be reduced to SAT in polynomial time ⓘ |
| literalDefinition | variable or its negation ⓘ |
| npCompletenessProofBy |
Leonid Levin
NERFINISHED
ⓘ
Stephen Cook NERFINISHED ⓘ |
| npCompletenessProofPublication | The Complexity of Theorem-Proving Procedures NERFINISHED ⓘ |
| npCompletenessProofYear | 1971 ⓘ |
| output | YES if the formula is satisfiable, NO otherwise ⓘ |
| practicalRelevance |
used in constraint solving
ⓘ
used in cryptanalysis ⓘ used in hardware verification ⓘ used in planning and scheduling ⓘ used in software verification ⓘ |
| reductionType | polynomial-time many-one reduction ⓘ |
| relatedProblem |
3-SAT
NERFINISHED
ⓘ
Hamiltonian cycle problem NERFINISHED ⓘ QBF (quantified Boolean formula problem) ⓘ circuit-SAT ⓘ clique problem ⓘ graph coloring ⓘ vertex cover ⓘ |
| restriction |
2-SAT is solvable in polynomial time
NERFINISHED
ⓘ
3-SAT is NP-complete ⓘ Horn-SAT is solvable in polynomial time ⓘ k-SAT for k ≥ 3 is NP-complete ⓘ |
| satisfiableIf | there exists at least one assignment making the formula true ⓘ |
| solvedBy | SAT solver ⓘ |
| typicalRepresentation | CNF formula as a conjunction of clauses ⓘ |
| unsatisfiableIf | no assignment makes the formula true ⓘ |
| valueDomain | {true,false} ⓘ |
| variableType | Boolean variable ⓘ |
| worstCaseComplexity | believed not solvable in polynomial time unless P = NP ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.