CounterexampleConstruction: AI-adaptedVerification: AI-adaptedPipeline-generatedaudited 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.

Relativized separations prove unrelativized separations

Statement refuted

The oracle-independent transfer schema refuted in Relativized separations prove unrelativized separations fails: a separating oracle cannot force separation in every other oracle world.

Facts & Assumptions

Given: the objects and hypotheses in the statement above.

[F1]

The refutation supplies total oracles $B$ and $A = T Q B F$ with $P^{B} \neq N P^{B}$ and $P^{A} = N P^{A}$ , respectively. These are counterinstances to the universal transfer rule; no conclusion about the empty oracle follows. (Relativized separations prove unrelativized separations).

Counterexample

1.1

Use the separating oracle $B$ and the equality oracle $A = T Q B F$ in the refutation of the schema. They satisfy $P^{B} \neq N P^{B}$ and $P^{A} = N P^{A}$ , respectively. Thus the premise holds while one instance of the universal conclusion fails.

2.1

The empty oracle is a third specified world. The exhibited failure at $A$ establishes invalidity of universal transfer, but gives no equality or inequality for the empty oracle. Hence this counterexample does not resolve the ordinary P-versus-NP problem.

step 1.1algebra∎

Depends on

Relativized separations prove unrelativized separations

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

3 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, pp71–72. (standard reference, not scraped)