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.1

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.

L1given

1.2

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.

given

1.3

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.

L2given

2.1

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.

step 1.1step 1.2step 1.3∎

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)