TheoremStatement: Literature-sourcedProof: AI-adaptedaudited 2026-09-07

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.

Graph nonisomorphism is in IP

Statement

$G N I = {(G_{0}, G_{1}) : G_{0} ≇ G_{1}}$ lies in $I P$ .

Proof

Given: the graph-nonisomorphism protocol.

1.1

If $G_{0} ≇ G_{1}$ , the isomorphism class of $H$ identifies the unique $b$ , so an unbounded prover answers correctly with probability $1$ .

given

1.2

If $G_{0} ≅ G_{1}$ , the distributions of $π (G_{0})$ and $π (G_{1})$ are identical; even conditioned on $H$ , $b$ is uniform, so every prover succeeds with probability $1 / 2$ . This verifies the protocol The graph-nonisomorphism interactive protocol.

given

2.1

Run two fresh independent challenges and accept only when both answers are correct. On a no instance, after every first transcript the second challenge is still independent and every response succeeds with conditional probability at most $1 / 2$ ; thus the two-copy soundness is at most $(1 / 2)^{2} = 1 / 4$ , while completeness remains $1$ . Hence The class IP applies.

step 1.1step 1.2algebra∎

Depends on

Used by

The graph-nonisomorphism protocol on a graph pair Example

Dependency tree · two levels

5 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, §8.3 (standard reference, not scraped)