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.
All labels observed (3)
| Label | Occurrences |
|---|---|
| Max-E3-LIN-2 canonical | 1 |
| Max-LIN-2 | 1 |
| Maximum Exact 3-Linear Equations Modulo 2 | 1 |
How this entity was disambiguated
This entity first appeared as the object of triple T5642218 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.
NED1
Entity disambiguation (via context triple)
gpt-5-mini-2025-08-07
Target entity: Max-E3-LIN-2 Context triple: [Inapproximability results for SAT and other problems, relatedConcept, Max-E3-LIN-2]
-
A.
Optimates
The Optimates were a conservative political faction in the late Roman Republic that championed senatorial authority and traditional aristocratic privileges against popular reformers like Julius Caesar.
-
B.
Lasserre
Lasserre is a small rural commune in southwestern France known for being the later-life home of the influential mathematician Alexander Grothendieck.
-
C.
E line
The E line is a rapid transit service of the New York City Subway that runs primarily along the IND Eighth Avenue Line in Manhattan and Queens.
-
D.
LPP
LPP is the IATA airport code for Lappeenranta Airport in Lappeenranta, Finland.
-
E.
Line 3
Line 3 is one of the main lines of the Barcelona Metro system, running through central parts of the city and connecting several key stations and neighborhoods.
- F. None of above. chosen
- G. Unsure - the case is ambiguous/there is not enough information to decide.
NED2
Entity disambiguation (via description)
gpt-5-mini-2025-08-07
Target entity: Max-E3-LIN-2 Target entity description: 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.
-
A.
Optimates
The Optimates were a conservative political faction in the late Roman Republic that championed senatorial authority and traditional aristocratic privileges against popular reformers like Julius Caesar.
-
B.
Lasserre
Lasserre is a small rural commune in southwestern France known for being the later-life home of the influential mathematician Alexander Grothendieck.
-
C.
E line
The E line is a rapid transit service of the New York City Subway that runs primarily along the IND Eighth Avenue Line in Manhattan and Queens.
-
D.
LPP
LPP is the IATA airport code for Lappeenranta Airport in Lappeenranta, Finland.
-
E.
Line 3
Line 3 is one of the main lines of the Barcelona Metro system, running through central parts of the city and connecting several key stations and neighborhoods.
- F. None of above. chosen
Statements (46)
| Predicate | Object |
|---|---|
| instanceOf |
NP-hard optimization problem
ⓘ
computational problem ⓘ constraint satisfaction optimization problem ⓘ |
| abbreviationOf |
Maximum Exact 3-Linear Equations Modulo 2
ⓘ
linked to:
Max-E3-LIN-2
|
| approximationClass | APX-hard ⓘ |
| baselineRandomAssignmentSatisfaction | 1/2 ⓘ |
| belongsToClass | Max-CSP ⓘ |
| 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 ⓘ
linked to:
Max-E3-LIN-2
|
| 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 ⓘ |
| relatedTo |
Label Cover
ⓘ
PCP theorem ⓘ |
| 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 ⓘ |
How these facts were elicited
The pipeline generated the facts above by prompting gpt-5.1 with this entity's name + description and the instruction below.
Instruction
You are a knowledge base construction expert. Given a subject entity and a description of it, return factual statements that you know for the subject as a JSON list of dictionaries(triples), where keys must be "subject", "predicate" and "object". The number of facts may be very high, between 25 to 50 or more, for very popular subjects. For less popular subjects, the number of facts can be very low, like 5 or 10. # Requirements - If you don't know the subject at all, return an empty list. - If the subject is not a named entity, return an empty list. - Include at least one triple where predicate is "instanceOf". - Do not get too wordy. - Separate several objects into multiple triples with one object.
Input
Subject: Max-E3-LIN-2 Description of subject: 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.
Referenced by (3)
Full triples — surface form annotated when it differs from this entity's canonical label.
subject linked to:
“Inapproximability results for SAT and other problems”
linked to: Max-E3-LIN-2
linked to: Max-E3-LIN-2