How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
Repeating constraints amplifies the gap
Statement
Duplicating every constraint of a CSP instance the same number of times strictly increases its unsatisfaction fraction.
Facts & Assumptions
Given: the value conventions of Constraint graph and labeling value and a nonzero number of repetitions .
A constraint system consists of a finite list of constraints; for a labeling the value is the fraction of listed constraints satisfied, so duplicated constraints count with multiplicity, and with (Constraint graph and labeling value).
Gap-preserving reductions are compared through unsatisfaction fractions, so any operation that preserves the fraction of violated constraints for every labeling preserves of the system (Complete uniform gap-preserving CSP reductions).
Refutation
Let have constraints and let be the system obtained by listing every constraint of exactly times, . If , both lists are empty and the value convention of [F1] gives unsatisfaction zero for every labeling in both systems. If , fix a labeling and let be the number of constraints of violated by : the list has constraints and exactly of them are violated, so ; taking the minimum over labelings gives , never a strict increase.
The failure is nonvacuous. Take the alphabet , the one-vertex constraint graph with the two loops of Constraint graph and labeling value: the loop carrying the relation , which every labeling of satisfies, and the loop carrying the empty relation , which every labeling violates. Then has constraints, every labeling violates exactly one of them, and ; after repeating each constraint times every labeling violates exactly of the listed constraints, so for every .
So the false statement fails at the witness of step 1.2 for every , and by step 1.1 no instance whatsoever has its unsatisfaction fraction changed by an equal repetition of its constraints. What an amplification step needs instead is a change of the variables and constraints, not a reweighting of the existing list: the powering of Constraint graph powering with local-view labels and the comparison families of the assignment-tester construction are of this genuinely different kind.
Depends on
Used by
- Duplicating constraints does not change UNSAT Counterexample
Dependency tree · two levels
4 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.
Sources
- Irit Dinur, The PCP theorem by gap amplification, §1.5 and the weight normalisation of constraints, printed pp. 4-6. (standard reference, not scraped)
- Arora and Barak, Computational Complexity: A Modern Approach, §18.5, printed pp. 370-375. (standard reference, not scraped)