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.
A single equality edge through robust composition
Example
Let be the graph with two vertices , alphabet and the single edge carrying the equality relation . For the satisfying labeling both endpoint blocks are set to the edge circuit accepts, every constraint of the composed tester gadget can be satisfied, and the binary-star conversion of that gadget has zero violated edges. The graph itself also has value one and unsatisfaction zero.
Facts & Assumptions
Given: The two-vertex, one-edge equality graph , its value-one labeling , the code of Shared codeword blocks and edge acceptance circuits, and the composition of Composition of an edge system with an assignment tester.
For , the Walsh–Hadamard table is indexed lexicographically by masks and evaluates ; in dimension one the masks are . (Walsh–Hadamard encoding and relative Hamming distance)
For the alphabet of size , the code uses and : the first two codewords are and . The edge circuit accepts exactly the pairs of valid blocks whose decoded labels lie in the edge relation, with loops tested diagonally. (Shared codeword blocks and edge acceptance circuits)
Graph value is the maximum satisfied edge fraction; for a graph with at least one edge a labeling has value one exactly when it satisfies every edge relation. (Constraint graph and labeling value)
For the composition , if then , with value one on an empty constraint list. (Composition preserves perfect satisfiability)
If , every edge of contributes exactly constraints of , where over the positive local gadget sizes; with a single edge and each local constraint is copied once. (Composition of an edge system with an assignment tester)
The conversion of a Boolean constraint system into a binary graph has perfect completeness: a labeling satisfying every input constraint extends to a graph labeling satisfying every output edge. It creates at most edges per listed constraint. (Bounded-arity Boolean constraints become binary graph constraints)
Verification
By [F1] the dimension-one table is evaluated at masks and , so with length , in agreement with the code selection of [F2].
The labeling is a graph labeling, and its ordered endpoint pair lies in ; since the equality edge is the only edge, and , so by [F3].
The block assigned to both endpoints is by [F2]. Both blocks are valid codewords and decode uniquely to the labels , whose ordered pair lies in ; hence the robust edge circuit accepts the displayed input by [F2].
Since , [F4] gives : some assignment to the variables of satisfies every constraint of . By [F5], the single edge contributes constraints, namely the constraints of the local two-piece tester copied once each; therefore one assignment satisfies every tester gadget constraint simultaneously.
Apply the conversion of [F6] to . The satisfying assignment of step 2.2 extends to a labeling of the output graph that satisfies every output edge, so the output has value one and unsatisfaction zero: the number of violated edges is . The conversion creates at most edge records and uses the fixed 66-symbol alphabet , so this is a concrete instance of the composition and conversion maps with no random or infinite selection anywhere.
Remarks
This is the smallest nontrivial instance of the completeness direction of Composition preserves perfect satisfiability: a satisfiable one-edge graph over the two-symbol alphabet, whose block code has length two. It illustrates that the composition and the binary-star conversion reproduce a satisfying labeling rather than merely preserving a value bound. The numeric verification uses only the displayed dot products and the two listed relation pairs; no claim is made about rejection probabilities, which require the separate soundness direction.
Depends on
- Composition preserves perfect satisfiability
- Composition of an edge system with an assignment tester
- Shared codeword blocks and edge acceptance circuits
- Bounded-arity Boolean constraints become binary graph constraints
- Walsh–Hadamard encoding and relative Hamming distance
- Constraint graph and labeling value
Used by
Nothing in the library uses this result yet.
Dependency tree · two levels
13 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, §5.1, Definition 5.1 and Lemma 1.8 (completeness direction), printed pp. 17–18 (standard reference, not scraped)
- Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, §18.5.2, proof of Lemma 18.30 (completeness direction), printed pp. 378–379 (standard reference, not scraped)