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.
The clause graph is an L-reduction with constants one and one
Example
On the Max-3SAT-to-independent-set clause-literal graph, the optimum values are equal and every independent set of size decodes to an assignment satisfying at least clauses. Hence this explicit map is an L-reduction with , and any independent-set approximation ratio transfers with the same relative error to Max-3SAT.
Facts & Assumptions
Given: The clause-literal consistency construction that carries a 3-CNF formula with clauses of three literal occurrences to a simple graph with vertices, with and with a polynomial-time decoder from independent sets to assignments.
Vertices of are the literal occurrences, vertices in a clause are pairwise adjacent, vertices from distinct clauses are adjacent exactly when their literals are complementary, for every such formula, and an independent set of size yields in polynomial time an assignment satisfying at least clauses. (Clause-literal consistency graph preserves the Max-3SAT optimum)
An L-reduction from optimization problem to consists of polynomial-time maps and and constants with and . (L-reductions between optimization problems)
If L-reduces to with constants , then a feasible solution of relative error at most decodes to a solution of relative error at most whenever the target optimum is positive, and zero target optimum forces an optimal decoded solution; consequently L-reductions transfer approximation quality. (L-reductions compose and transfer PTAS and APX-hardness)
Both Max-3SAT and maximum independent set are maximization problems in the finite-instance model: the value of a feasible solution is nonnegative, and the optimum is the attained maximum, so a feasible solution's quality is measured by how far its value falls below the optimum. (Optimization problems and approximation ratios, Clique, independent set, and vertex cover decision problems)
Verification
Take the instance map of [F1], which runs in polynomial time and produces a finite simple graph whose independent sets have value . Take the decoder of [F1], which from every independent set of produces in polynomial time an assignment of satisfying at least clauses, of value equal to its satisfied-clause count. Both objectives are maximization with nonnegative values by [F4].
The first L-reduction inequality holds with : by the exact optimum equality of [F1], for every 3-CNF formula with three literal occurrences per clause.
The second L-reduction inequality holds with : writing for the number of clauses satisfied by the decoded assignment, [F1] gives , and therefore , where the last step uses and step 2.1.
Steps 2.1 and 3.1 exhibit the maps and constants required by [F2], so is an L-reduction from Max-3SAT to maximum independent set. By the transfer statement [F3], a feasible independent set with relative error at most , that is , decodes to a Max-3SAT assignment with relative error at most ; when the decoded assignment is optimal.
A concrete formula is with clauses of three literal occurrences. No assignment satisfies both clauses: true satisfies only the first and false satisfies only the second, so . The graph has vertices in two clause clusters of three; an independent set takes at most one vertex per cluster, and every vertex of the first cluster is complementary to every vertex of the second, so no independent set has size , while a single vertex is independent; hence , and an independent set of size decodes to an assignment satisfying at least clause.
The explicit clause-literal construction therefore is an L-reduction with constants : the optimum values agree, and every independent set of size decodes to an assignment satisfying at least clauses, so errors transfer unchanged and an independent-set approximation ratio carries over to Max-3SAT with the same relative error.
Depends on
- Optimization problems and approximation ratios
- APX-hardness and APX-completeness under L-reductions
- Clique, independent set, and vertex cover decision problems
- L-reductions between optimization problems
- Clause-literal consistency graph preserves the Max-3SAT optimum
- L-reductions compose and transfer PTAS and APX-hardness
Used by
Nothing in the library uses this result yet.
Dependency tree · two levels
12 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
- Arora and Barak, Computational Complexity: A Modern Approach, §18.2.5 Lemma 18.16, printed pp. 359–361 (standard reference, not scraped)
- Williamson and Shmoys, The Design of Approximation Algorithms, §16.2 Definition 16.4 and Theorems 16.5–16.6, printed pp. 413–414 (standard reference, not scraped)