PropositionStatement: Literature-sourcedProof: AI-generatedprecheck passaudited 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.

Polynomial-time and polynomial-space computation are invariant across standard machine models

Statement

For deterministic single-tape and fixed-multitape Turing-machine models, the notions of polynomial-time computation and polynomial-space computation define the same language classes.

Facts & Assumptions

Given: A language decided on one of the two standard deterministic Turing-machine models named in the statement.

[L1]

Multitape time- $T$ computations have single-tape simulations in $O ((n + T (n))^{2})$ time, by Every multitape time-T computation has a single-tape simulation in $O ((n + T (n))^{2})$ time.

[L2]

Multitape space- $S$ computations have single-tape simulations in $O (n + S (n))$ space, by Every multitape space-S computation has a single-tape simulation in O(n+S(n)) space.

Proof

technique · direct

1.1L1given

Suppose a language is decided by a deterministic multitape machine in time bounded by a polynomial $p (n)$ . By [L1], there is a single-tape decider running in time $O ((n + p (n))^{2})$ , and $(n + p (n))^{2}$ is still a polynomial. Thus polynomial time on multitape machines implies polynomial time on one tape.

1.2given

Conversely, every one-tape machine is already a special case of a multitape machine, so any one-tape polynomial-time algorithm is automatically a multitape polynomial-time algorithm.

1.3L2given

For space, [L2] shows that a multitape polynomial-space decider has a single-tape decider using $O (n + s (n))$ space, which is still polynomial whenever $s$ is polynomial. The reverse implication is immediate because one tape is a special multitape case.

2.1step 1.1step 1.2step 1.3∎

Steps 1.1 and 1.2 prove model invariance for polynomial time, and step 1.3 proves it for polynomial space. Therefore the two standard models define the same polynomial-time and polynomial-space language classes.

Depends on

Used by

FALSE: machine invariance means equivalent models perform exactly the same number of steps False statement

Dependency tree · two levels

7 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, 7. Time Complexity (standard reference, not scraped)