ExampleConstruction: AI-adaptedVerification: 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.

Perfect completeness through a TQBF reduction

Example

Take the IP language $L = T Q B F$ with the identity reduction, so that an input is already a quantified Boolean formula, and take the true instance $Φ = \exists x (x), b (X) = X,$ for which $n = 1$ , the matrix has $L = 1$ syntax node, $D = 2$ and $T = 2$ . The protocol parameters of The Shamir interactive protocol for TQBF are $N = \max {2, 12 T D + 1} = 49$ and $p = 53$ , the first admissible integer above $49$ , so the field is $Z / 53$ . Running the honest prover, in the round for $E_{X}$ it sends the message $T \mapsto T$ and in the round for $R_{X}$ it again sends $T \mapsto T$ ; for arbitrary challenges $r, r^{'} \in Z / 53$ both verifier tests pass, the claim chain is $1 \to r \to r^{'}$ , and the terminal comparison is $b (r^{'}) = r^{'}$ . Hence the honest prover is accepted on every random tape, which is perfect completeness on this instance.

Facts & Assumptions

Given: The language TQBF with the identity reduction, the true instance $Φ = \exists x (x)$ , and an arbitrary pair of challenges $r, r^{'}$ in the field chosen by the protocol.

[A1]

Every language in IP has an interactive proof with perfect completeness and soundness error at most $1 / 3$ , obtained by moving the language into PSPACE and using the TQBF reduction protocol (IP admits perfect completeness).

[A2]

TQBF has such a protocol: on true inputs the honest prover is accepted with probability one, on false inputs every prover is accepted with probability at most $2 T D / p < 1 / 3$ , and TQBF lies in IP (TQBF has a polynomial-round interactive proof, Total TQBF soundness by the first repaired claim).

[A3]

For a formula with $n$ variables and $L$ matrix nodes the protocol uses $T = n (n + 3) / 2$ , $D = \max {L, 2}$ , $N = \max {2, 12 T D + 1}$ and the first admissible integer in $(N, 2 N)$ , which is prime; messages are coefficient lists of degree at most $D$ , the claim starts at $1$ , the verifier tests $c = s (0) s (1)$ , $c = s (0) + s (1) - s (0) s (1)$ or $c = (1 - a) s (0) + a s (1)$ according to the node, samples a fresh challenge after the message, sets $c : = s (r)$ , and accepts exactly when $c = b (σ)$ (The Shamir interactive protocol for TQBF, A polynomial-size prime field meets the soundness budget).

[A4]

The classes of $Z / 53$ and of $Z / 101$ form fields, so each nonzero residue has an inverse and the arithmetic below is modular (For every prime $p$ , the two operations on $Z / p$ make it a field).

Verification

1.1

For $Φ = \exists x (x)$ we have $n = 1$ , $L = 1$ , hence $D = \max {1, 2} = 2$ and $T = 1 \cdot 4 / 2 = 2$ ; then $N = \max {2, 12 \cdot 2 \cdot 2 + 1} = 49$ , and the integers $50, 51, 52$ are inadmissible because $50 = 2 \cdot 25$ , $51 = 3 \cdot 17$ and $52 = 2 \cdot 26$ have divisors at most $49$ , so the first admissible integer is $p = 53$ , which is prime by [A3].

A3algebra

1.2

The operator list of $Φ$ is $R_{X}, E_{X}$ , so the stage polynomials are $G_{0} = b = X$ , $G_{1} = R_{X} X = (1 - X) \cdot 0 + X \cdot 1 = X$ and $G_{2} = E_{X} X = 1 - (1 - 0) (1 - 1) = 1$ ; the last value is the truth value of the true formula $Φ$ , and the protocol processes the nodes in the reverse order $E_{X}$ , then $R_{X}$ .

A3givenalgebra

2.1

In the round for $E_{X}$ the claim is $c = 1$ and the honest message is the restriction of $G_{1}$ , namely $s (T) = T$ . The existential test reads $s (0) + s (1) - s (0) s (1) = 0 + 1 - 0 = 1 = c$ , so it passes; the verifier then draws its challenge $r$ , sets $σ (x) = r$ and $c = s (r) = r$ .

A3step 1.2algebra

3.1

In the round for $R_{X}$ the current value of the reduced variable is $a = σ (x) = r$ and the honest message is the restriction of $G_{0}$ , again $s (T) = T$ . The reduction test reads $(1 - a) s (0) + a s (1) = (1 - r) \cdot 0 + r \cdot 1 = r = c$ , so it passes; the verifier draws a fresh challenge $r^{'}$ , sets $σ (x) = r^{'}$ and $c = s (r^{'}) = r^{'}$ .

A3step 2.1algebra

4.1

The terminal comparison is $c = b (σ) = r^{'}$ , which holds; so for every pair $(r, r^{'})$ of challenges the honest prover is accepted, and since the challenges range over all of $Z / 53 \times Z / 53$ the acceptance probability is $1$ . This is an instance of the perfect completeness asserted in [A1] and [A2].

A2A3step 3.1A4

5.1

For contrast, the false instance $Φ^{'} = \exists x (x \land \neg x)$ has matrix $X (1 - X)$ with $L = 4$ syntax nodes, so $D = 4$ , $T = 2$ , $N = 97$ and the protocol prime is $101$ ; the soundness bound of [A2] evaluates there as $2 T D / p = 16 / 101 < 1 / 3$ . This numerical evaluation quotes the theorem's bound and does not reprove soundness.

A2A4algebra∎

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

31 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, §8.5.3, author-hosted draft (standard reference, not scraped)
A. Shen, IP = PSPACE: Simplified Proof, JACM 39(4) 1992, pp. 878–880 (standard reference, not scraped)