Alphabeta Math
TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck passaudited 2026-09-27
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

PSPACE⊆IP: every language in PSPACE has an interactive proof with perfect completeness and soundness error at most 1/3, whose verifier is a probabilistic polynomial-time machine with polynomially many rounds and polynomially bounded communication. Explicitly, for L∈PSPACE there is a polynomial-time computable reduction f with x∈L if and only if f(x)∈TQBF, and the protocol that runs the verifier of TQBF has a polynomial-round interactive proof on f(x) is such a proof for L.

Facts & Assumptions

Given: A language L in PSPACE.

[A1]

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).

[A2]

TQBF has an interactive proof with a probabilistic polynomial-time verifier, perfect completeness and soundness error at most 1/3; the verifier's running time, round count and communication are polynomial in its input length (TQBF has a polynomial-round interactive proof).

[A3]

A language lies in IP when it has an interactive protocol with a probabilistic polynomial-time verifier, polynomially bounded interaction, completeness at least 2/3 and soundness at most 1/3 (The class IP).

Proof technique: direct.

Proof

1.1

By [A1] there is a polynomial-time computable map f with x∈L if and only if f(x)∈TQBF; since f runs in polynomial time, there is a polynomial q with ∣f(x)∣≤q(∣x∣) for every input x.

A1given
2.1

Define the verifier VL for L as follows: on input x, compute Φx:=f(x) deterministically and then run the TQBF verifier V of [A2] on input Φx, forwarding the prover's messages to V and V's messages to the prover. Since f is computable in polynomial time and V runs in time polynomial in ∣Φx∣≤q(∣x∣), the machine VL is a probabilistic polynomial-time machine, and the protocol has polynomially many rounds and polynomially bounded communication because those bounds for V are polynomial in ∣Φx∣.

step 1.1A2construct
2.2

If x∈L then Φx∈TQBF by step 1.1, so by [A2] the honest prover for V on Φx, used as the prover for VL, is accepted with probability one, in particular at least 2/3.

step 1.1A2
2.3

If x∉L then Φx∉TQBF by step 1.1, so by [A2] every prover for V on input Φx is accepted with probability at most 1/3; a prover for VL on x induces such a prover for V on Φx, the reduction being deterministic, so no prover for VL exceeds 1/3.

step 1.1A2given
3.1

Steps 1.1 and 2.1 exhibit for L a probabilistic polynomial-time verifier with polynomially bounded interaction, and steps 2.2 and 2.3 give completeness 1≥2/3 and soundness at most 1/3; hence L∈IP by [A3]. Since L was an arbitrary language in PSPACE, PSPACE⊆IP, with perfect completeness for every language in the class.

step 2.1step 2.2step 2.3A3given∎

Depends on

Used by

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