LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck passjudge pass (gpt-6-sol)audited 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.

Total TQBF soundness by the first repaired claim

Statement

Let $Φ$ be a false closed prenex quantified Boolean formula, with $n$ variables, matrix length $L$ , and the parameters $T = n (n + 3) / 2$ , $D = \max {L, 2}$ and prime $p$ of its Shamir protocol. Then for every prover strategy the probability that the verifier of The Shamir interactive protocol for TQBF accepts is at most $2 T D / p$ , which is less than $1 / 6$ and hence at most $1 / 3$ . A randomized prover is allowed, its coins being independent of the verifier's future challenges.

Facts & Assumptions

Given: A false closed prenex quantified Boolean formula $Φ$ , its Shamir protocol, and an arbitrary prover strategy.

[A1]

The rounds run for $t = T, T - 1, \dots, 1$ ; in each round the verifier assigns its freshly drawn challenge to the active variable of the round's node, so the sequence of points depends on the verifier's random tape alone and not on the prover's messages; after the last round the verifier accepts exactly when the current claim equals the matrix value $b$ at the current point (The Shamir interactive protocol for TQBF).

[A2]

For each round $t$ , conditional on a reached prefix with $c_{t} \neq G_{t} (σ_{t})$ and on a fixed message passing the round's check, the probability that the updated claim equals the true predecessor value is at most $2 D / p$ (A false field claim becomes true in one round with bounded probability).

[A3]

If $T \geq 1$ , the prime satisfies $p > 12 T D$ by A polynomial-size prime field meets the soundness budget; if $T = 0$ , the protocol sets $p = 3 > 12 T D = 0$ (The Shamir interactive protocol for TQBF).

[A4]

The final stage constant $G_{T}$ equals the truth value of $Φ$ , embedded in $F$ as $0$ or $1$ , and the initial stage polynomial is $G_{0} = b$ ; for the false $Φ$ this gives $G_{T} = 0 \neq 1$ (The ordered arithmetization evaluates to the quantified Boolean truth value).

Proof technique: direct calculation.

Proof

1.1

Because the point sequence follows the fixed round schedule from the verifier's random tape alone by [A1], the points are well defined for every prover; the stage polynomials $G_{t}$ depend only on variables that the schedule has already assigned when round $t$ begins, so the true values $v_{t} : = G_{t} (σ_{t})$ are well-defined random variables on the verifier's tape, and $v_{T} = G_{T} = 0$ .

A1A4given

2.1

The run begins with the claim $c_{T} = 1$ ; by step 1.1 the initial claim is false, that is $c_{T} \neq v_{T}$ , and this holds pointwise for every random tape and every prover.

step 1.1A1given

2.2

For $t = 1, \dots, T$ let $B_{t}$ be the event that the run reaches round $t$ with $c_{t} \neq v_{t}$ , that the round's message passes its check, and that $c_{t - 1} = v_{t - 1}$ . By [A2] the conditional probability of the transition, given any such reached prefix and any fixed message passing the check, is at most $2 D / p$ ; averaging over the reached prefixes and over the prover's randomization gives $\Pr [B_{t}] \leq 2 D / p$ .

step 1.1A2algebra

3.1

If the verifier accepts, every check passed and the terminal test $c_{0} = b (σ_{0})$ holds; since $G_{0} = b$ by [A4], this says $c_{0} = v_{0}$ . Together with step 2.1 this forces the claim to pass from false to true at some round, so the acceptance event is contained in $⋃_{t = 1}^{T} B_{t}$ . Pointwise the indicator of this union is at most the sum of the indicators, and averaging gives $\Pr [accept] \leq \sum_{t} \Pr [B_{t}] \leq T \cdot 2 D / p = 2 T D / p$ .

step 2.1step 2.2A1A4algebra

4.1

By [A3] we have $2 T D / p < 2 / 12 = 1 / 6$ , and $1 / 6 < 1 / 3$ , so the acceptance probability of every prover on the false input $Φ$ is at most $1 / 3$ . If $n = 0$ then $T = 0$ , there are no rounds, the terminal test compares $1$ with $G_{0} = G_{T} = 0$ and fails, and the acceptance probability $0$ equals the bound $2 T D / p$ ; if a prover randomizes, its coins are fixed before the challenge that decides $B_{t}$ and the averaging of step 2.2 already covers it.

step 3.1A3A4algebra∎

Depends on

Used by

Perfect completeness through a TQBF reduction Example
False: the verifier can trust the final field value False statement
TQBF has a polynomial-round interactive proof Theorem

Dependency tree · two levels

17 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

A. Shen, IP = PSPACE: Simplified Proof, JACM 39(4) 1992, pp. 878–880 (standard reference, not scraped)
Arora and Barak, Computational Complexity: A Modern Approach, §8.5.3, author-hosted draft (standard reference, not scraped)