Alphabeta MathThe IP = PSPACE 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.
✓ 17 results · all verified · 11 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 6 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.
1 · Prerequisites
Abstract Algebra
Combinatorics
Computability Theory
- Arithmetization and the Sum-Check Protocol
- Formal Languages, Encodings, and Decision Problems
- Interactive Proof Systems and Public Coins
- P, NP, coNP, and Polynomial Reductions
- Resource Bounds and Machine Invariance
- Space Complexity, Savitch's Theorem, and TQBF
- Turing Machines, Configurations, and Computation
Linear Algebra
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
- 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
- Suprema and Infima
- The Derivative and the Mean Value Theorems
- The Exponential Function
- The Logarithm and General Powers
- The Riemann Integral: Definition and Integrability
- Topology of ℝ
Set Theory
2 · Logical flowchart
3 · Items
Definition
Field arithmetization of QBF quantifiers
Lemma
Quantifier polynomials agree with QBF semantics on Boolean assignments
Definition
Multilinearization in one variable
Lemma
Multilinearization preserves Boolean values and bounds individual degree
Lemma
The ordered arithmetization evaluates to the quantified Boolean truth value
Lemma
A polynomial-size prime field meets the soundness budget
Definition
The Shamir interactive protocol for TQBF
Lemma
Honest prover maintains the field-value claim
Lemma
Explicit communication, round, and evaluation bounds
Lemma
Shamir protocol has perfect completeness
Lemma
A false field claim becomes true in one round with bounded probability
Lemma
Total TQBF soundness by the first repaired claim
Lemma
Shamir verifier runs in polynomial time
Theorem
TQBF has a polynomial-round interactive proof
Theorem
PSPACE is contained in IP
Theorem
IP equals PSPACE
Corollary
IP is closed under complement
Theorem
IP admits perfect completeness
False statement
False: IP = PSPACE needs no degree reduction in this arithmetization
False statement
False: the verifier can trust the final field value
Sources
- Arora and Barak, Computational Complexity: A Modern Approach, §8.5, author-hosted draft
- A. Shen, IP = PSPACE: Simplified Proof, JACM 39(4) 1992, pp. 878–880
- Arora and Barak, Computational Complexity: A Modern Approach, §8.5.3 and Remark 8.19, author-hosted draft
- Arora and Barak, Computational Complexity: A Modern Approach, §8.5.2 (prime p in (2^n, 2^{2n}]) and §8.5.3, author-hosted draft
- A. Shen, IP = PSPACE: Simplified Proof, JACM 39(4) 1992, pp. 878–880 ("p can be chosen by P or V because primality testing is trivial for numbers of this size")
- A. Shen, IP = PSPACE: Simplified Proof, JACM 39(4) 1992, pp. 878–880, §2 (protocol B and its three cases A, E, R)
- Arora and Barak, Computational Complexity: A Modern Approach, §8.5.3, author-hosted draft
- Arora and Barak, Computational Complexity: A Modern Approach, Theorem 8.17 and §8.5.3, author-hosted draft
- Arora and Barak, Computational Complexity: A Modern Approach, Theorem 8.17 and §8.5, author-hosted draft
- Arora and Barak, Computational Complexity: A Modern Approach, Theorem 8.17, author-hosted draft
- Arora and Barak, Computational Complexity: A Modern Approach, §8.5 and the remarks after Theorem 8.17, author-hosted draft
- Arora and Barak, Computational Complexity: A Modern Approach, §8.5.3 (perfect completeness of the TQBF protocol), author-hosted draft
- Arora and Barak, Computational Complexity: A Modern Approach, §8.5.3 (degree growth warning) and Remark 8.19, author-hosted draft