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.
PSPACE is contained in IP
Statement
: every language in PSPACE has an interactive proof with perfect completeness and soundness error at most , whose verifier is a probabilistic polynomial-time machine with polynomially many rounds and polynomially bounded communication. Explicitly, for there is a polynomial-time computable reduction with if and only if , and the protocol that runs the verifier of TQBF has a polynomial-round interactive proof on is such a proof for .
Facts & Assumptions
Given: A language in PSPACE.
TQBF is PSPACE-complete: TQBF lies in PSPACE and every language in PSPACE polynomial-time many-one reduces to TQBF, a reduction being a polynomial-time computable map that preserves yes and no instances exactly (TQBF is PSPACE-complete).
TQBF has an interactive proof with a probabilistic polynomial-time verifier, perfect completeness and soundness error at most ; the verifier's running time, round count and communication are polynomial in its input length (TQBF has a polynomial-round interactive proof).
A language lies in when it has an interactive protocol with a probabilistic polynomial-time verifier, polynomially bounded interaction, completeness at least and soundness at most (The class IP).
Proof technique: direct.
Proof
By [A1] there is a polynomial-time computable map with if and only if ; since runs in polynomial time, there is a polynomial with for every input .
Define the verifier for as follows: on input , compute deterministically and then run the TQBF verifier of [A2] on input , forwarding the prover's messages to and 's messages to the prover. Since is computable in polynomial time and runs in time polynomial in , the machine is a probabilistic polynomial-time machine, and the protocol has polynomially many rounds and polynomially bounded communication because those bounds for are polynomial in .
If then by step 1.1, so by [A2] the honest prover for on , used as the prover for , is accepted with probability one, in particular at least .
If then by step 1.1, so by [A2] every prover for on input is accepted with probability at most ; a prover for on induces such a prover for on , the reduction being deterministic, so no prover for exceeds .
Steps 1.1 and 2.1 exhibit for a probabilistic polynomial-time verifier with polynomially bounded interaction, and steps 2.2 and 2.3 give completeness and soundness at most ; hence by [A3]. Since was an arbitrary language in PSPACE, , with perfect completeness for every language in the class.
Depends on
Used by
- IP admits perfect completeness Theorem
- IP equals PSPACE Theorem
Dependency tree · two levels
18 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, Theorem 8.17 and §8.5, author-hosted draft (standard reference, not scraped)
- A. Shen, IP = PSPACE: Simplified Proof, JACM 39(4) 1992, pp. 878–880 (standard reference, not scraped)