Alphabeta MathAlphabet Reduction and the PCP Theorem
About this page
Pipeline-generated
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.
✓ 26 results · all verified · 12 also independently AI-judged
Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 14 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.
1 · Prerequisites
Abstract Algebra
- Algebraic Closure, Embeddings, and Separability
- Algebraic Extensions, Extension Degree, and Finite Fields
- Binary Operations, Monoids, Groups and Subgroups
- Composition Series, the Jordan–Hölder Theorem and Solvable Groups
- Cosets, Index and Lagrange's Theorem
- Cyclic Groups and Direct Products
- Divisibility, Euclidean Domains, Principal Ideal Domains and Unique Factorisation
- Group Actions, Orbits, Stabilisers and Cayley's Theorem
- Group Homomorphisms and the Isomorphism Theorems
- Ideals, Quotient Rings and the Isomorphism Theorems for Rings
- Normal Subgroups and Quotient Groups
- Polynomial Rings, the Division Algorithm and Roots
- Rings, Subrings, Integral Domains and Fields
- Simple Field Extensions and the Construction of the Complex Numbers
- Splitting Fields
- Sylow's Theorems, p-Groups and Nilpotent Groups
- The Fundamental Theorem of Algebra
- The Fundamental Theorem of Finite Abelian Groups
- The Galois Correspondence
Combinatorics
Computability Theory
- Arithmetization and the Sum-Check Protocol
- Boolean Circuits and Nonuniform Complexity
- Expander Graphs and Constraint Graphs
- Formal Languages, Encodings, and Decision Problems
- Gap Amplification and Assignment Testing
- P, NP, coNP, and Polynomial Reductions
- Resource Bounds and Machine Invariance
- The Cook--Levin Theorem
- Turing Machines, Configurations, and Computation
Linear Algebra
- Determinants of Matrices over a Commutative Ring
- Diagonalisation and the Minimal Polynomial
- Dual Spaces, Bilinear and Quadratic Forms, and Sylvester's Law of Inertia
- Eigenvalues, Eigenvectors and the Characteristic Polynomial
- Inner Product Spaces, Gram-Schmidt, Projections and Adjoints
- Linear Independence, Bases and Dimension
- Linear Transformations, Rank-Nullity and Quotient Spaces
- Matrices, the Matrix of a Linear Map, and Change of Basis
- The Determinant of a Linear Operator, Cofactors and Cramer's Rule
- The Spectral Theorem, Positive Operators and Singular Value Decomposition
- Triangularisation, Generalised Eigenspaces and Jordan Canonical Form
- Vector Spaces, Linear Subspaces, Span and Direct Sums
Number Theory
Real Analysis
- Absolute and Conditional Convergence; Rearrangement; Products
- Construction of the Real Numbers via Cauchy Sequences
- Construction of the Real Numbers via Dedekind Cuts
- Continuity, IVT, EVT, and Uniform Continuity
- Countability and Uncountability
- Foundations of the Real Numbers for Analysis
- Limits of Real Functions
- limsup, liminf, and Subsequential Limits
- Monotone Functions, Discontinuities, and Continuity Sets
- Monotone Sequences, Bolzano-Weierstrass, and Cauchy Completeness
- pi: the Equivalent Characterizations
- Power Series and Real-Analytic Functions
- Properties of the Integral and the Working FTC
- Roots, Rational Powers, and Classical Inequalities
- Sequences and Limits
- Sequences and Series of Functions; Uniform Convergence
- Series: Convergence and the Nonnegative Tests
- Sine, Cosine, and the Definition of Pi
- Suprema and Infima
- The Derivative and the Mean Value Theorems
- The Riemann Integral: Definition and Integrability
- Topology of ℝ
Set Theory
2 · Logical flowchart
3 · Items
Definition
PCP verifier resources and deterministic proof strings
Definition
PCP classes with completeness and soundness
Lemma
Two-query PCPs and binary constraint graphs
Definition
Walsh–Hadamard encoding and relative Hamming distance
Lemma
Distinct Walsh–Hadamard words differ on half the cube
Definition
Shared codeword blocks and edge acceptance circuits
Lemma
A violated decoded edge is far from edge-circuit acceptance
Lemma
Random binary subsums detect every nonzero discrepancy
Definition
Quadratic equations and tensor-code oracle tables
Lemma
Boolean circuits become quadratic systems with a fixed input prefix
Lemma
The BLR test supplies a nearby unique linear decoder
Lemma
Tensor consistency rejects a wrong decoded tensor
Lemma
A random subsum checks all quadratic equations at once
Theorem
An exponential-length constant-query PCP for quadratic equations
Definition
Two-piece PCP of proximity and concatenation check
Lemma
Concatenation testing enforces the same decoded prefix
Theorem
A two-piece constant-query PCP of proximity
Definition
Composition of an edge system with an assignment tester
Lemma
Composition preserves perfect satisfiability
Lemma
Composition transfers a constant fraction of unsatisfaction
Lemma
Bounded-arity Boolean constraints become binary graph constraints
Theorem
Fixed-alphabet reduction with constant gap retention
Lemma
Alphabet reduction controls explicit size and degree
Definition
One fixed-alphabet Dinur transformation
Lemma
One Dinur transformation preserves perfect satisfiability
Lemma
One fixed-alphabet transformation doubles small gaps
Lemma
One fixed transformation has constant-factor growth
Lemma
Logarithmic iteration reaches a constant unsatisfaction gap
Lemma
A three-CNF formula as a fixed-alphabet binary constraint graph
Theorem
Constant-gap binary CSP is NP-hard
Theorem
The PCP theorem: NP equals PCP(log n, O(1))
Theorem
PCP soundness amplification by independent repetition
False statement
False: graph powering alone keeps the alphabet fixed
False statement
False: a PCP proof is itself a random string
Sources
- Irit Dinur, The PCP Theorem by Gap Amplification
- Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach
- Arora and Barak, Computational Complexity: A Modern Approach, §18.2.4, proof of Theorem 18.13 in both directions, printed pp. 358–359
- Arora and Barak, Computational Complexity: A Modern Approach, §18.4.1, printed p. 363
- Arora and Barak, Computational Complexity: A Modern Approach, §18.4.1 and §18.5.2 proof of Lemma 18.30, printed pp. 363–364 and 378–379
- Irit Dinur, The PCP Theorem by Gap Amplification, §5 proof of Lemma 1.8, printed pp. 18–19
- Arora and Barak, Computational Complexity: A Modern Approach, §18.4.2 random subsum principle and its applications, printed pp. 366–367
- Arora and Barak, Computational Complexity: A Modern Approach, §18.4.2, proof of Theorem 18.21, printed pp. 365–366
- Arora and Barak, Computational Complexity: A Modern Approach, §18.4.3, proof of Corollary 18.25, printed p. 368; §18.4.2, QUADEQ encoding, printed pp. 365–366
- Arora and Barak, Computational Complexity: A Modern Approach, §18.4.1 Theorem 18.23 and local decoding, printed pp. 363–365; §19.3.2 proof of Theorem 19.9, printed pp. 390–391
- Arora and Barak, Computational Complexity: A Modern Approach, §18.4.2 proof of Theorem 18.21 Step 2, printed pp. 366–367
- Arora and Barak, Computational Complexity: A Modern Approach, §18.4.2, proof of Theorem 18.21 Step 3, printed p. 367
- Arora and Barak, Computational Complexity: A Modern Approach, §§18.4.1–18.4.2 proof of Theorem 18.21, Steps 1–3, printed pp. 363–367
- Arora and Barak, Computational Complexity: A Modern Approach, §18.4.3, Corollaries 18.25–18.26 and proof of Corollary 18.25, printed pp. 368–369
- Arora and Barak, Computational Complexity: A Modern Approach, §18.4.3, concatenation test and Corollary 18.26, printed pp. 368–369
- Arora and Barak, Computational Complexity: A Modern Approach, §18.4.3, concatenation test and Corollary 18.26, printed pp. 368–369 (PDF pp. 384–385)
- Irit Dinur, The PCP Theorem by Gap Amplification, §5.1, Definition 5.1 (composition), Lemma 1.8 and its proof
- Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, §18.5.2, Corollary 18.35 and proof of Lemma 18.30
- Irit Dinur, The PCP Theorem by Gap Amplification, §5, Lemma 1.8 and proof (perfect-completeness direction)
- Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, §18.5.2, Corollary 18.35 and proof of Lemma 18.30 (completeness direction)
- Irit Dinur, The PCP Theorem by Gap Amplification, §5 proof of Lemma 1.8, printed pp. 17–18
- Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, §18.5.2 Corollary 18.35 and proof of Lemma 18.30, printed pp. 378–379
- Irit Dinur, The PCP Theorem by Gap Amplification, §5, Lemma 1.8 and its proof, printed pp. 17–19
- Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, §18.5, Lemma 18.30 and §18.5.2, printed pp. 377–379
- Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, §18.5.2, Lemma 18.30 and its proof, printed pp. 378–379
- Irit Dinur, The PCP Theorem by Gap Amplification, §1.3, Theorems 1.2 and 1.5 and §3 proof of Theorem 1.5, printed pp. 5–8 and 12–15
- Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, §18.5.1 Lemma 18.29 and §18.5.2 Lemma 18.30, printed pp. 371–379
- Irit Dinur, The PCP Theorem by Gap Amplification, §1.3, Theorems 1.2 and 1.5 (completeness direction), printed pp. 5–8
- Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, §18.5.1 Lemma 18.29 (completeness), printed pp. 371–373
- Irit Dinur, The PCP Theorem by Gap Amplification, §1.3 Theorem 1.5 (Main), soundness clause and fixed output alphabet, printed pp. 4–5
- Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, §18.5.1 gap amplification (Lemma 18.29) and §18.5.2 alphabet reduction (Lemma 18.30), printed pp. 370–379
- Irit Dinur, The PCP Theorem by Gap Amplification, §1.3 Theorem 1.5 (size clause size(G′) ≤ C·size(G)), printed pp. 4–5
- Irit Dinur, The PCP Theorem by Gap Amplification, §1.3 Theorem 1.5 and the logarithmic-iteration paragraph, printed pp. 4–5
- Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, §18.5 (iteration of Lemma 18.28 log m times), printed p. 370
- Irit Dinur, The PCP Theorem by Gap Amplification, §1.3 Theorem 1.2 (inapproximability form, printed p. 3) and Theorem 1.5 (printed pp. 4–5)
- Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, §18.5 (reduction from qCSP to GAP qCSP), printed pp. 370–371
- Irit Dinur, The PCP Theorem by Gap Amplification, §1.3 Theorems 1.1, 1.2 and 1.5, printed pp. 2–5
- Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, §18.1–18.2 (PCP and NP) and §18.5 (proof of the PCP theorem), printed pp. 350–379
- Arora and Barak, Computational Complexity: A Modern Approach, §18.1, Note 3 to Theorem 18.2, printed p. 354
- Irit Dinur, The PCP Theorem by Gap Amplification, §1.1, printed pp. 1–2
- Arora and Barak, Computational Complexity: A Modern Approach, §18.1, Definition 18.1, printed pp. 353–354