Max-3-SAT
E537214
Max-3-SAT is an optimization variant of the Boolean satisfiability problem where the goal is to maximize the number of satisfied clauses, each containing exactly three literals, and it serves as a central problem in the study of approximation algorithms and hardness of approximation.
Statements (44)
| Predicate | Object |
|---|---|
| instanceOf |
computational problem
ⓘ
constraint satisfaction problem ⓘ |
| basedOn | 3-SAT NERFINISHED ⓘ |
| clauseType | disjunction of three literals ⓘ |
| complexityClass | NP-hard ⓘ |
| decisionVersion | is there an assignment satisfying at least k clauses? ⓘ |
| expectedSatisfiedFractionUnderRandomAssignment | 7/8 ⓘ |
| formulaStructure | conjunction of 3-literal clauses ⓘ |
| generalizationOf | 3-SAT ⓘ |
| hasAlternativeObjectiveFunction | fraction of satisfied clauses ⓘ |
| hasApproximationAlgorithm | randomized 7/8-approximation ⓘ |
| hasApproximationGuarantee | no polynomial-time algorithm can beat 7/8 + ε under P≠NP (for some formulations) ⓘ |
| hasApproximationRatio | 7/8 by random assignment ⓘ |
| hasConstraint | each clause has exactly three literals ⓘ |
| hasInput | 3-CNF formula ⓘ |
| hasObjective | maximize number of satisfied clauses ⓘ |
| hasRandomizedBaseline | assign each variable true or false independently with probability 1/2 ⓘ |
| hasReductionFrom | 3-SAT NERFINISHED ⓘ |
| hasReductionTo |
Max-Cut (via standard transformations in hardness proofs)
ⓘ
Max-SAT NERFINISHED ⓘ |
| hasTypicalObjectiveFunction | number of satisfied clauses ⓘ |
| hasVariableDomain | Boolean variables ⓘ |
| isCentralIn |
design of randomized approximation algorithms
ⓘ
study of inapproximability ⓘ |
| isRobustVariantOf | 3-SAT with respect to unsatisfiable instances ⓘ |
| isSpecialCaseOf |
Max-CSP
NERFINISHED
ⓘ
Max-k-SAT NERFINISHED ⓘ |
| literalType | variable or its negation ⓘ |
| optimizationCriterion | maximize satisfied clauses rather than satisfy all ⓘ |
| output |
maximum number of satisfiable clauses
ⓘ
truth assignment ⓘ |
| relatedTo |
3-SAT
ⓘ
Boolean satisfiability problem NERFINISHED ⓘ Max-SAT NERFINISHED ⓘ approximation algorithms ⓘ hardness of approximation ⓘ |
| searchSpace | all truth assignments to Boolean variables ⓘ |
| studiedIn |
approximation complexity
ⓘ
probabilistically checkable proofs ⓘ theory of NP-completeness ⓘ |
| usedAs |
benchmark problem in approximation algorithms
ⓘ
canonical problem for PCP-based hardness results ⓘ |
| usedFor |
demonstrating tight PCP theorems
ⓘ
reductions to other approximation problems ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.
subject surface form:
Inapproximability results for SAT and other problems