ExampleConstruction: AI-adaptedVerification: AI-adaptedPipeline-generatedjudge pass (gpt-5.6-terra)audited 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.

Relativization alone cannot resolve p versus np

Example

A TQBF oracle absorbs polynomial nondeterministic computation into PSPACE. A finite diagonal stage with clock $p (n) = n^{2}$ and $n = 8$ can defeat a machine on $1^{8}$ , provided all earlier committed words have length less than eight. This finite stage is not a complete separating oracle.

Facts & Assumptions

Given: the objects and hypotheses in the statement above.

[F1]

Neither an argument for $P = N P$ nor an argument for $P \neq N P$ can be valid unchanged relative to every total oracle. (Relativization alone cannot resolve p versus np).

[F2]

$N P^{T Q B F} \subseteq P S P A C E \subseteq P^{T Q B F}$ . (Polynomial space oracle absorption).

Verification

1.1

A branch has at most polynomially many queries, all of polynomial length. Replaying the finite branch tree and deciding each TQBF query in reusable polynomial space gives the absorption; one many-one TQBF reduction supplies the converse PSPACE inclusion into deterministic oracle time.

2.1

At $n = 8$ there are $256$ candidate words and at most $64$ queries. Preserve earlier commitments and answer every new query NO. At least $192$ length-eight words remain unqueried. An accepting run is defeated by freezing the entire length to NO; a rejecting run by setting one unqueried word YES and freezing the rest NO. Also freeze every queried word of other lengths. Further stages are required to defeat other programs. Opposite full oracle worlds, not this one finite count alone, yield the relativization obstruction.

F1algebra∎

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

6 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–Barak, Computational Complexity, 2007 draft; §3.5 proof of Theorem3.9, pp71–72. (standard reference, not scraped)