Max-E3-LIN-2
E537215
Max-E3-LIN-2 is a canonical constraint satisfaction optimization problem over linear equations modulo 2 with three variables per equation, widely used as a central example in hardness of approximation theory.
Statements (46)
| Predicate | Object |
|---|---|
| instanceOf |
NP-hard optimization problem
ⓘ
computational problem ⓘ constraint satisfaction optimization problem ⓘ |
| abbreviationOf | Maximum Exact 3-Linear Equations Modulo 2 NERFINISHED ⓘ |
| approximationClass | APX-hard ⓘ |
| baselineRandomAssignmentSatisfaction | 1/2 ⓘ |
| belongsToClass | Max-CSP NERFINISHED ⓘ |
| centralTo | probabilistically checkable proofs (PCP) theory ⓘ |
| complexityStatus | NP-hard to solve exactly ⓘ |
| constraintLanguage | all 3-variable linear equations over GF(2) ⓘ |
| constraintType | linear equation ⓘ |
| definedOver | linear equations modulo 2 ⓘ |
| equationForm | x ⊕ y ⊕ z = b (mod 2) ⓘ |
| field | GF(2) ⓘ |
| hardnessOfBeatingRandom | it is NP-hard to approximate better than 1/2 + ε for some ε > 0 under standard assumptions ⓘ |
| hasApproximationResistance | yes ⓘ |
| hasCanonicalStatus | yes ⓘ |
| hasConstraintArity | 3 variables per equation ⓘ |
| hasConstraintSize | 3 ⓘ |
| hasDecisionVariant | given threshold k, is there an assignment satisfying at least k equations? ⓘ |
| hasDomain | {0,1} ⓘ |
| hasGapVersion | distinguish nearly satisfiable instances from highly unsatisfiable ones ⓘ |
| hasInput | set of linear equations over GF(2) with exactly 3 variables each ⓘ |
| hasOperation | addition modulo 2 ⓘ |
| hasOutput | assignment to variables ⓘ |
| hasRandomizedAlgorithmBaseline | random assignment satisfies about half the equations ⓘ |
| hasSymmetry | invariance under variable negation and permutation within each equation ⓘ |
| isBooleanCSP | true ⓘ |
| isMaximizationProblem | true ⓘ |
| isSpecialCaseOf |
Max-3-CSP
ⓘ
Max-LIN-2 NERFINISHED ⓘ |
| isUniformVariant | each constraint has exactly 3 variables ⓘ |
| modulus | 2 ⓘ |
| objective | maximize number of satisfied equations ⓘ |
| optimizationCriterion | number of satisfied constraints ⓘ |
| relatedProblem |
Max-3-SAT
ⓘ
Max-Cut NERFINISHED ⓘ |
| relatedTo |
Label Cover
NERFINISHED
ⓘ
PCP theorem NERFINISHED ⓘ |
| studiedIn |
approximation algorithms
ⓘ
computational complexity theory ⓘ |
| typicalUse | starting point for gap-introducing reductions ⓘ |
| usedAs | canonical example in PCP-based inapproximability ⓘ |
| usedFor | reductions in inapproximability proofs ⓘ |
| usedIn | hardness of approximation theory ⓘ |
| variableType | Boolean variables ⓘ |
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