CorollaryStatement: Literature-sourcedProof: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-12

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.

PSPACE equals NPSPACE and is closed under complement

Statement

$P S P A C E = N P S P A C E,$

and if $L \in P S P A C E$ then its complement also lies in PSPACE.

Facts & Assumptions

Given: the classes PSPACE and NPSPACE.

[L1]

PSPACE and NPSPACE are the unions of $D S P A C E (p (n))$ and $N S P A C E (p (n))$ over polynomial bounds $p$ (The classes PSPACE and NPSPACE).

[L2]

Savitch's theorem gives $N S P A C E (s (n)) \subseteq D S P A C E (s (n)^{2})$ for every $s$ (Savitch's theorem: NSPACE(s(n)) is contained in DSPACE(s(n)^2)).

[L3]

A deterministic space class is defined by deterministic deciders (The classes DTIME, NTIME, DSPACE, and NSPACE).

Proof

technique · direct

1.1

If $L \in N P S P A C E$ , then [L1] gives a polynomial $p$ with $L \in N S P A C E (p (n))$ . By [L2], $L \in D S P A C E (p (n)^{2}) \subseteq P S P A C E$ , because the square of a polynomial is again a polynomial. Thus $N P S P A C E \subseteq P S P A C E$ .

L1L2given

2.1

The reverse inclusion $P S P A C E \subseteq N P S P A C E$ is immediate from [L1] because every deterministic machine is a special case of a nondeterministic one. Hence $P S P A C E = N P S P A C E$ .

L1step 1.1

3.1

If $L \in P S P A C E$ , choose a deterministic polynomial-space decider $M$ for $L$ using [L1] and [L3]. Swapping the accepting and rejecting halting states of $M$ gives a deterministic polynomial-space decider for the complement of $L$ . Therefore PSPACE is closed under complement.

L1L3construct∎

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

9 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

Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach (standard reference, not scraped)
Eric Blais, Models of Computation, 17. Space Complexity (standard reference, not scraped)