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

A machine that runs in O(n^2) time necessarily uses at most O(n^2) space

Example

Let $M$ be a decider that, on an input of length $n$ , makes at most $3 n^{2} + 5 n + 7$ steps. For instance, $M$ might repeatedly sweep across the input while keeping only a bounded amount of auxiliary control information. Then the time-bound lemma implies that the total number of visited tape cells is also at most a constant multiple of $n^{2}$ .

Facts & Assumptions

Given: A machine $M$ with running time at most $3 n^{2} + 5 n + 7$ on inputs of length $n$ .

[L1]

Any $O (T (n))$ time bound yields an $O (T (n))$ space bound for a fixed machine, by A time bound always yields the same-order space bound.

Verification

technique · direct

1.1

The polynomial $3 n^{2} + 5 n + 7$ is $O (n^{2})$ . So the hypothesis places $M$ in the setting of [L1] with $T (n) = n^{2}$ .

given

2.1

Applying [L1] yields ${Space}_{M} (n) = O (n^{2})$ . This matches the concrete intuition that a machine cannot visit more than a constant multiple of its own number of time steps.

L1step 1.1∎

Depends on

A time bound always yields the same-order space bound

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

4 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

Eric Blais, Models of Computation, 17. Space Complexity (standard reference, not scraped)