Deterministic Complexity Classes

DTIME, DSPACE, P, and hierarchy ideas for deterministic computation.

Goals

• Define $\mathrm{DTIME}$, $\mathrm{DSPACE}$, and $\mathrm P$.
• Prove basic containments from resource bounds.
• Understand why constructibility matters in hierarchy theorems.

Intuition

A class groups languages by an asymptotic resource budget. Unions over polynomial bounds avoid committing to a particular exponent and remain stable under polynomial simulation.

Formal definitions

$\mathrm{DTIME}(t(n))$ and $\mathrm{DSPACE}(s(n))$ contain languages decidable by deterministic machines within those bounds. Define

The other standard deterministic unions are

Some books write $\mathrm{EXPTIME}$ for $\mathrm{EXP}$. The union absorbs fixed polynomial exponents but not a change from polynomial to exponential growth. All definitions concern worst-case bounds on halting deciders.

Read solid arrows as proved containments, not equalities. The basic chain is

Claim. $\mathrm P\subseteq\mathrm{PSPACE}$.

Proof walkthrough

Fix $k\ge1$ and prove $\mathrm{DTIME}(n^k)\subseteq\mathrm{DSPACE}(n^k)$. Let $L\in\mathrm{DTIME}(n^k)$, and let $M$ be a deterministic decider that halts within $n^k$ steps on every input of length $n$.

Each step moves a work head by at most one cell. Therefore a run of at most $n^k$ steps visits at most $n^k$ work cells (up to a constant for bookkeeping absorbed in $O$). Hence $L\in\mathrm{DSPACE}(n^k)$.

Since this holds for every $k$,

The union closes the claim: no single exponent is required for all of $\mathrm P$.

What this does not show. It does not prove $\mathrm P=\mathrm{PSPACE}$, nor any separation. It also does not yield a tight space bound for a specific problem beyond the simulation.

The deterministic time hierarchy theorem says, under suitable time-constructibility and gap conditions, that more time decides strictly more languages. Its diagonal simulation needs enough extra time to interpret and simulate encoded machines.

Configuration counting and containments

Let a fixed deterministic machine use $s(n)\ge\log n$ work space. A configuration records its constant-size state, $O(s(n))$ work symbols, work-head positions, and an input-head position among $n+1$ locations. Therefore there are at most

configurations. A halting deterministic run cannot repeat one: repetition would force an infinite loop. Hence, after adding a configuration counter (or detecting repeats), a space-$s(n)$ decider halts within $2^{O(s(n))}$ steps, so

Claim. $\mathrm{PSPACE}\subseteq\mathrm{EXP}$.

Proof. Let $L\in\mathrm{PSPACE}$. Then for some $k$, $L\in\mathrm{DSPACE}(n^k)$. By the inclusion above,

There is a constant $c$ with time at most $2^{c n^k}$. For a large enough exponent $k'$ (e.g. $k'=k+1$), $c n^k\le n^{k'}$ for all large $n$, hence $L\in\mathrm{DTIME}(2^{n^{k'}})\subseteq\mathrm{EXP}$.

The elementary fact that time bounds space gives $\mathrm{EXP}\subseteq\mathrm{EXPSPACE}$. Together with $\mathrm P\subseteq\mathrm{PSPACE}$ this yields

These inclusions do not establish whether adjacent classes are equal. Hierarchy theorems do imply $\mathrm P\subsetneq\mathrm{EXP}$ and $\mathrm{PSPACE}\subsetneq\mathrm{EXPSPACE}$, but they do not resolve $\mathrm P$ versus $\mathrm{PSPACE}$.

Constructibility

A function $t(n)\ge n$ is time-constructible if a deterministic TM, on an input of length $n$, can produce or count exactly $t(n)$ steps within $O(t(n))$ time. A function $s(n)\ge\log n$ is space-constructible if a machine can mark exactly $s(n)$ work cells using $O(s(n))$ space. Standard bounds such as $n^k$, $2^n$, and $2^{n^k}$ satisfy appropriate constructibility conditions.

Constructibility lets the diagonal machine enforce its budget. Without it, a pathological numerical function may be large but not efficiently recognizable as a resource limit. The condition is therefore operational, not cosmetic.

Deterministic time hierarchy

One standard formulation says: if $t_1,t_2$ are time-constructible and

then

for a standard multitape model. Exact logarithmic factors depend on simulation conventions.

Proof walkthrough

1. Enumerate encoded deterministic machines $M_1,M_2,\ldots$ and arrange that descriptions occur at infinitely many padded lengths.
2. Define a diagonal decider $D$ on input $x$ of length $n$. Interpret part of $x$ as a machine description; malformed descriptions get a fixed answer.
3. Use time constructibility to start a $t_2(n)$-step clock.
4. Universally simulate the encoded $M$ on $x$ for enough steps to cover its claimed $t_1(n)$ computation, including the simulator's logarithmic overhead.
5. If the simulation accepts in budget, reject; otherwise accept.
6. The gap condition ensures that interpretation, clocking, and simulation fit in $O(t_2(n))$, so $L(D)\in\mathrm{DTIME}(t_2)$.
7. Suppose some $t_1$-time machine $M_i$ decides $L(D)$. Choose a sufficiently long padded input encoding $M_i$. The simulation completes, and $D$ returns the opposite of $M_i$ on that same input, a contradiction.

The proof does not flip an answer after an unbounded simulation. The timeout and gap are exactly what make $D$ a decider in the larger class.

Application. For every fixed $k$,

under a suitable constructible formulation, because $n^k\log n=o(n^{k+1.1})$. To derive $\mathrm P\subsetneq\mathrm{EXP}$, diagonalize against all polynomial exponents within an exponential budget, or use a standard corollary of the hierarchy theorem.

Deterministic space hierarchy

A standard space hierarchy theorem says that if $s_1,s_2$ are space-constructible, at least logarithmic, and $s_1=o(s_2)$, then

Proof walkthrough

1. Enumerate machines and use padded descriptions as diagonal inputs.
2. The diagonal machine reserves $O(s_2(n))$ cells and simulates the encoded machine without crossing that boundary.
3. A simulation that attempts too much space is cut off.
4. A machine might loop while staying inside the boundary, so a simple timer of $s_2(n)$ bits is insufficient. Instead count the at most $2^{O(s_2(n))}$ bounded configurations using $O(s_2(n))$ counter bits.
5. If the simulated machine halts, reverse its answer; if it exceeds the configuration count, it has repeated and can be treated as nonhalting.
6. Space constructibility supplies the boundary, and the $o$ gap allows bookkeeping and self-interpretation.
7. On a padded encoding of any purported $s_1$-space decider for the diagonal language, the output disagrees with itself.

Taking the union over polynomial versus exponential constructible bounds yields

Padding

Padding changes the relation between the meaningful instance size and total input length. For language $L$ and increasing padding function $p$, define

If $N=p(n)$, an algorithm costing $2^{O(n)}$ on $x$ may become polynomial in padded length $N$ when $p(n)=2^{\Theta(n)}$. The padded language is a different language; padding does not magically speed up the original problem.

Example. If $L\in\mathrm{DTIME}(2^{n})$, then on an input promised to have the form $x\#1^{2^{|x|}-|x|}$, simulate the original decider in $2^{|x|}=O(N)$ time after checking the format. Thus the padded version lies in $\mathrm P$. Parsing and validating the padding must be included.

Padding arguments can transfer hypothetical containments or equalities between scales. Their proof obligations are: define a uniquely parseable format, relate $n$ and $N$, verify membership, and translate the resource bound in the correct direction.

Worked example

Graph reachability is in $\mathrm P$: breadth-first search marks each vertex once and scans edges in polynomial time. The marks and queue also use polynomial space, illustrating the containment above.

Common mistakes

• Reading $\mathrm P$ as “fast in practice.”
• Assuming $\mathrm{DTIME}(n^2)\subsetneq\mathrm{DTIME}(n^3)$ without checking hierarchy hypotheses.
• Using a runtime bound that excludes non-halting branches.
• Treating a containment diagram as proof of strictness.
• Omitting constructibility or the hierarchy gap.
• Forgetting loop detection in a space-bounded diagonal simulation.
• Claiming padding places the original, unpadded language in a smaller class.

Visualization prompt

Draw nested regions $\mathrm P\subseteq\mathrm{PSPACE}\subseteq\mathrm{EXPTIME}$; annotate known containments separately from unknown equalities.

Exercises

Exercise 1 — $\mathrm{DTIME}(n^k)\subseteq\mathrm{DSPACE}(n^k)$

Prove explicitly that for every $k\ge1$, $\mathrm{DTIME}(n^k)\subseteq\mathrm{DSPACE}(n^k)$, and deduce $\mathrm P\subseteq\mathrm{PSPACE}$.

Exercise 2 — Placing a language in the chain

Language $L$ has a decider using $n^3$ work cells. Prove $L\in\mathrm{PSPACE}$ and $L\in\mathrm{EXP}$. What cannot be concluded about membership in $\mathrm P$?

Exercise 3 — Time-hierarchy audit

Does the standard time-hierarchy theorem (with $t_1\log t_1=o(t_2)$) directly prove

Explain. Show how to separate $n^2$ from $n^3$ under the same hypotheses.

Exercise 4 — Padding algebra

Suppose original time $2^{n^2}$ and padded length $N=2^n$. Prove the time as a function of $N$ is not polynomial. Which padding would make the simulation linear in $N$?

Exercise 5 — Polynomial versus quasipolynomial

Prove that $2^{O(\log n)}$ is polynomial in $n$, but $2^{O((\log n)^2)}$ need not be.

Summary

Deterministic classes formalize scalable resource budgets. Elementary simulation gives containments, while diagonalization—under constructibility conditions—gives separations.

Guided theorem audit

Task 1 — Is the proof valid?

A student claims: “$\mathrm{DTIME}(n^2)\subsetneq\mathrm{DTIME}(n^2\log n)$ because there is more time.” List the missing steps in the hierarchy proof template, and what can be salvaged.

Task 2 — Space-bound audit

A decider uses $n^2$ cells. Bound the number of configurations and the halting time. When may one replace $2^{O(n^2)}$ by $2^{n^2}$?

Task 3 — Capstone: chain, hierarchy, and padding

1. Explain why proving $\mathrm P\subsetneq\mathrm{EXP}$ cannot pick a single polynomial exponent.
2. With padding $N=n^4$, translate times $n^{12}$ and $2^n$ to the new length.
3. What distinguishes an existential class separation from classifying a natural problem in $\mathrm{EXP}\setminus\mathrm P$?

Sources

• Student-summary evidence: merged course summary, pp. 6-24, 30, 36-39, 68-71, 107, and 129-135; used for course emphasis, not verification.
• Course evidence: Semester A 2026 transcripts 2-4, deterministic classes, constructibility, and hierarchy arguments.
• Verification: Sipser, 3e, pp. 275-279 and 321-335.
• Verification: Arora-Barak draft, pp. 65-88.
• Verification: Papadimitriou, pp. 139-154.