Alphabeta Math
ExampleConstruction: AI-generatedVerification: AI-adaptedPipeline-generatedprecheck passjudge pass (gpt-6.1-sol)audited 2026-10-02
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 k decodes to an assignment satisfying at least k clauses. Hence this explicit map is an L-reduction with a=b=1, 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 F with m clauses of three literal occurrences to a simple graph GF with 3m vertices, with α(GF)=OPT⁡Max3SAT(F) and with a polynomial-time decoder from independent sets to assignments.

[F1]

Vertices of GF are the literal occurrences, vertices in a clause are pairwise adjacent, vertices from distinct clauses are adjacent exactly when their literals are complementary, α(GF)=OPT⁡Max3SAT(F) for every such formula, and an independent set of size k yields in polynomial time an assignment satisfying at least k clauses. (Clause-literal consistency graph preserves the Max-3SAT optimum)

[F2]

An L-reduction from optimization problem Π to Γ consists of polynomial-time maps f and g and constants a,b>0 with OPT⁡Γ(f(x))≤aOPT⁡Π(x) and ∣OPT⁡Π(x)−val⁡Π(g(x,y))∣≤b∣OPT⁡Γ(f(x))−val⁡Γ(y)∣. (L-reductions between optimization problems)

[F3]

If Π L-reduces to Γ with constants a,b, then a feasible Γ solution of relative error at most ϵ decodes to a Π solution of relative error at most abϵ 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)

[F4]

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

technique · direct
1.1F1F2F4givenconstruct

Take the instance map f(F):=GF of [F1], which runs in polynomial time and produces a finite simple graph whose independent sets have value val⁡Γ(I)=∣I∣. Take the decoder g(F,I) of [F1], which from every independent set I of GF produces in polynomial time an assignment of F satisfying at least ∣I∣ clauses, of value val⁡Π(g(F,I)) equal to its satisfied-clause count. Both objectives are maximization with nonnegative values by [F4].

2.1F1step 1.1algebra

The first L-reduction inequality holds with a=1: by the exact optimum equality of [F1], OPT⁡Γ(f(F))=α(GF)=OPT⁡Max3SAT(F)=1⋅OPT⁡Π(F) for every 3-CNF formula F with three literal occurrences per clause.

3.1F1step 1.1step 2.1algebra

The second L-reduction inequality holds with b=1: writing t:=val⁡Π(g(F,I)) for the number of clauses satisfied by the decoded assignment, [F1] gives t≥∣I∣, and therefore ∣OPT⁡Π(F)−val⁡Π(g(F,I))∣=OPT⁡Max3SAT(F)−t≤OPT⁡Max3SAT(F)−∣I∣=α(GF)−∣I∣=∣OPT⁡Γ(f(F))−val⁡Γ(I)∣, where the last step uses val⁡Γ(I)=∣I∣ and step 2.1.

4.1F2F3step 2.1step 3.1algebra

Steps 2.1 and 3.1 exhibit the maps and constants required by [F2], so (f,g,1,1) 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 val⁡Γ(I)≥(1−ϵ)α(GF), decodes to a Max-3SAT assignment with relative error at most 1⋅1⋅ϵ=ϵ; when α(GF)=0 the decoded assignment is optimal.

5.1F1step 2.1step 4.1algebra

A concrete formula is F=(x∨x∨x)∧(¬x∨¬x∨¬x) with m=2 clauses of three literal occurrences. No assignment satisfies both clauses: x true satisfies only the first and x false satisfies only the second, so OPT⁡Max3SAT(F)=1. The graph GF has 6 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 2, while a single vertex is independent; hence α(GF)=1=OPT⁡Max3SAT(F), and an independent set of size 1 decodes to an assignment satisfying at least 1 clause.

6.1F3step 4.1step 5.1algebra∎

The explicit clause-literal construction therefore is an L-reduction with constants a=b=1: the optimum values agree, and every independent set of size k decodes to an assignment satisfying at least k clauses, so errors transfer unchanged and an independent-set approximation ratio carries over to Max-3SAT with the same relative error.

Depends on

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