3-SAT
E679892
3-SAT is a classic Boolean satisfiability problem where each clause has exactly three literals and which serves as a fundamental NP-complete benchmark in computational complexity theory.
Statements (46)
| Predicate | Object |
|---|---|
| instanceOf |
Boolean satisfiability problem
ⓘ
decision problem ⓘ |
| averageCaseStudy | phase transition in satisfiability around critical clause-to-variable ratios ⓘ |
| benchmarkRole |
benchmark for NP-completeness reductions
ⓘ
standard test problem in SAT solving ⓘ |
| canonicalStatus | canonical NP-complete problem ⓘ |
| clauseLength | 3 ⓘ |
| clauseType | disjunction of exactly three literals ⓘ |
| completeness | NP-complete ⓘ |
| complexityClass | NP NERFINISHED ⓘ |
| decisionQuestion | is the given 3-CNF formula satisfiable ⓘ |
| definedOver | Boolean formulas in conjunctive normal form ⓘ |
| field |
computational complexity theory
ⓘ
mathematical logic ⓘ theoretical computer science ⓘ |
| formulaType | conjunction of clauses ⓘ |
| generalizationOf | problems with clauses of at most three literals ⓘ |
| hardness | NP-hard ⓘ |
| historicalResult | first problems shown NP-complete via polynomial-time reduction from SAT ⓘ |
| importance |
central example in NP-completeness theory
ⓘ
fundamental benchmark in computational complexity theory ⓘ |
| inputEncoding | 3-CNF formula ⓘ |
| introducedIn | Cook–Levin theorem NERFINISHED ⓘ |
| optimizationVariant | MAX-3-SAT ⓘ |
| outputType | yes-no decision ⓘ |
| question | whether there exists a truth assignment that satisfies all clauses ⓘ |
| reductionType | polynomial-time many-one reduction ⓘ |
| relatedProblem |
2-SAT
ⓘ
3-CNF-SAT ⓘ MAX-3-SAT NERFINISHED ⓘ SAT ⓘ k-SAT ⓘ |
| representation | 3-CNF formula with n variables and m clauses ⓘ |
| restrictionOf | SAT NERFINISHED ⓘ |
| satisfiabilityType | exactly three literals per clause ⓘ |
| searchVariant | finding a satisfying assignment ⓘ |
| specialCaseOf | k-SAT for k = 3 ⓘ |
| statusIfPEqualsNP | would be solvable in polynomial time ⓘ |
| statusIfPNotEqualNP | believed not solvable in polynomial time ⓘ |
| typicalAlgorithmicApproach |
DPLL-based SAT solvers
ⓘ
backtracking search ⓘ local search algorithms ⓘ |
| typicalUse |
benchmark for SAT solver performance
ⓘ
starting point for NP-completeness proofs ⓘ |
| variableDomain | Boolean variables ⓘ |
| verificationProperty | candidate satisfying assignment can be verified in polynomial time ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.