Complexity — DTIME, DSPACE, complexity classes: Exercises

The two resources, once and for all, so no symbol is unearned:

$n = ∣ w ∣$ = the length (number of characters) of the input string $w$ .
Time = number of computation steps. Space = number of distinct tape cells the head ever visits.
$DTIME (f)$ = languages a deterministic Turing machine decides in $O (f (n))$ steps.
$DSPACE (f)$ = languages decided in $O (f (n))$ cells. Swap $D \to N$ for the guessing (nondeterministic) versions.

Definition Machine model used on this page (read this first — it makes every "cell count" precise)

Because space bounds like $lo g n$ are smaller than the input itself, we must fix the model carefully, exactly as in Turing Machines:

We use a multi-tape Turing machine: one read-only input tape holding $w$ , plus one or more read/write work tapes.
Space = the number of distinct cells scanned on the work tapes only. The input tape is not charged — otherwise nothing could ever use less than $n$ space and $L$ would be meaningless. This is the standard convention that lets $lo g n$ -space classes exist.
Time = total steps across all tapes.
A single-tape machine is the special case with one read/write tape that also holds the input; there space is at least $n$ . Whenever an exercise says "cell $i$ " (Ex 2.1, 2.2, 3.1, 2.3) it means a cell on a work tape, and counters are stored on work tapes so their bits are charged.

Encoding notation: $⟨ M ⟩$ means "the description of machine $M$ written out as a finite string" — its states, transitions and alphabet spelled as symbols. A machine can read another machine's code just like any other input. We use this in Level 5.

Figure — Complexity — DTIME, DSPACE, complexity classes

Level 1 — Recognition

Exercise 1.1

Fill the blanks: $DTIME (f (n))$ is a set of == (languages / numbers / machines), and the "D" stands for ==.

Recall Solution

$DTIME (f (n))$ is a set of languages (decision problems), not single problems and not machines. The D stands for deterministic — at every step the next move is uniquely forced, no guessing. (Contrast: N = nondeterministic, which may branch.)

Exercise 1.2

Which resource does each class budget — time or space? $P$ , $L$ , $PSPACE$ , $NP$ , $EXP$ , $NL$ .

Recall Solution

$P$ — time (polynomial steps, $⋃_{k} DTIME (n^{k})$ ).
$L$ — space ( $DSPACE (lo g n)$ , work-tape cells only).
$PSPACE$ — space ( $⋃_{k} DSPACE (n^{k})$ ).
$NP$ — time (nondeterministic, $⋃_{k} NTIME (n^{k})$ ).
$EXP$ — time ( $⋃_{k} DTIME (2^{n^{k}})$ ).
$NL$ — space ( $NSPACE (lo g n)$ ).

Mnemonic: the letter L or SPACE in the name = space; P, NP, EXP = time.

Exercise 1.3

True or false: $P \subseteq PSPACE$ . Give the one-line reason.

Recall Solution

True. In $f (n)$ steps a work-tape head moves at most one cell per step, so it visits at most $f (n) + 1$ work cells. Hence time $f \Rightarrow$ space $\leq f$ , i.e. $DTIME (f) \subseteq DSPACE (f)$ . Taking the union over $f = n^{k}$ gives $P \subseteq PSPACE$ . In the ring picture (s01), the $P$ ring sits inside the $PSPACE$ ring — that is exactly this inclusion.

Level 2 — Application

Exercise 2.1

A 2-tape TM (read-only input tape + one work tape) decides palindromes by comparing input cell $i$ with input cell $n - 1 - i$ for $i = 0, 1, \dots$ . Give a tight time bound as a $Θ (\cdot)$ and name the smallest standard time class containing it.

Recall Solution

Upper bound $O (n^{2})$ . There are about $n /2$ comparisons. To align input head $i$ against input head $n - 1 - i$ the head must sweep up to $n$ cells, so each comparison costs $O (n)$ steps. Total $\frac{n}{2} \cdot O (n) = O (n^{2})$ .

Lower bound $Ω (n^{2})$ (for this single-work-tape algorithm). After matching one pair, the head must travel from position $\approx n - 1 - i$ back toward position $i + 1$ to start the next comparison — a traversal of length $Θ (n)$ done $Θ (n)$ times. No reordering avoids these long head trips on one work tape, so at least $Ω (n^{2})$ steps are forced.

Conclusion. Both bounds meet, so this algorithm is $T (n) = Θ (n^{2}),$ hence palindromes $\in DTIME (n^{2}) \subseteq P$ ; the smallest standard time class is $P$ . (A different, cleverer 2-tape machine that first copies the input reversed onto the work tape reaches $Θ (n)$ time — tightness above is a statement about the given comparison algorithm, not a lower bound on the problem.)

Exercise 2.2

Same palindrome problem, but count space: the machine stores two counters $i$ and $n - 1 - i$ on its work tape. How many bits does a counter holding a value up to $n$ need, and which space class results?

Recall Solution

A counter whose value can reach $n$ needs $⌈ lo g_{2} (n + 1)⌉ = O (lo g n)$ bits — because binary uses one bit per doubling. Two such counters (on the work tape, so they are charged as space) is still $O (lo g n)$ ; the input tape holding $w$ is read-only and not charged. So palindromes $\in DSPACE (lo g n) = L$ .

Concrete check: for $n = 1000$ , a counter needs $⌈ lo g_{2} 1001 ⌉ = 10$ bits. Two counters = $20$ bits of work tape — tiny, no matter how big the string is.

Exercise 2.3

Reachability: given a directed graph $G$ on $n$ nodes and nodes $s, t$ (all on the read-only input tape), decide if $t$ is reachable from $s$ . Describe an $NL$ machine and state exactly what it stores on its work tape.

Recall Solution

$G$ , $s$ , $t$ sit on the read-only input tape (free). The nondeterministic machine keeps only two things on its work tape (both charged):

the current node (an index in ${1, \dots, n}$ ) — $O (lo g n)$ bits,
a step counter counting up to $n$ — $O (lo g n)$ bits.

Repeatedly: guess a neighbour of the current node (checking the edge against the input tape), move there, increment the counter. Accept if the current node equals $t$ ; reject if the counter exceeds $n$ (a simple path visits $\leq n$ nodes, so no honest path is longer). Total work-tape space $O (lo g n)$ ⇒ Reachability $\in NL$ . We never store the whole path — that is the whole trick.

Level 3 — Analysis

Exercise 3.1

Prove from first principles: $DSPACE (f (n)) \subseteq DTIME (2^{O (f (n))})$ for $f (n) \geq lo g n$ . Explain each factor in the configuration count and show why the polynomial factors vanish into the exponent.

Recall Solution

A configuration is a complete snapshot of the machine: (current state, positions of the input head and work head, contents of the $f (n)$ used work cells). Count how many distinct snapshots exist: $# configs \leq states ∣ Q ∣ \cdot input head (n + 1) \cdot work head f (n) \cdot work tape ∣Γ ∣^{f (n)} .$

$∣ Q ∣$ : finitely many control states — a constant.
$n + 1$ : the read-only input head can sit over one of $n + 1$ input positions.
$f (n)$ : the work head sits in one of $f (n)$ used work cells.
$∣Γ ∣^{f (n)}$ : each of $f (n)$ work cells holds one of $∣Γ∣$ tape symbols.

Why the polynomial factors are absorbed. Take $lo g_{2}$ of the whole product: $lo g_{2} (# configs) \leq O (1) lo g_{2} ∣ Q ∣ + O (l o g n) lo g_{2} (n + 1) + O (l o g f) lo g_{2} f (n) + O (f (n)) f (n) lo g_{2} ∣Γ∣ .$ Because $f (n) \geq lo g n$ , the term $f (n) lo g_{2} ∣Γ∣ = Θ (f (n))$ dominates every other term (each of the others is $O (lo g n) \leq O (f (n))$ or smaller). So the whole logarithm is $O (f (n))$ , which means $# configs \leq 2^{O (f (n))} .$ A halting machine never repeats a configuration (a repeat means an infinite loop). So its number of steps is at most the number of configurations, $2^{O (f (n))}$ . Hence it runs in $DTIME (2^{O (f (n))})$ . Bounded space forces bounded time.

Exercise 3.2

Using Ex 3.1, explain why $PSPACE \subseteq EXP$ but not the reverse inclusion is known, and why this places $NP$ inside $PSPACE$ .

Recall Solution

Set $f (n) = n^{k}$ (polynomial space). Ex 3.1 gives running time $2^{O (n^{k})}$ , which is exactly the $EXP$ budget $2^{n^{k^{'}}}$ . Taking unions: $PSPACE \subseteq EXP$ . In s01 the $PSPACE$ ring sits inside the $EXP$ ring.

The reverse ( $EXP \subseteq PSPACE$ ) is not known and is believed false — an exponential-time machine may genuinely need exponentially many cells.

$NP \subseteq PSPACE$ : an $NP$ problem has certificates of length $n^{k}$ . Deterministically try all $2^{n^{k}}$ certificates one at a time, reusing the same $n^{k}$ work cells for each attempt. Only polynomial space is ever occupied — the exponential blow-up is in time, not space. See Space vs Time Tradeoffs.

Exercise 3.3

State Savitch's Theorem and use it to bound the deterministic space cost of Reachability (from Ex 2.3).

Recall Solution

Savitch: $NSPACE (f (n)) \subseteq DSPACE (f (n)^{2})$ for $f \geq lo g n$ . The engine: reachability within $\leq 2^{m}$ steps splits at a midpoint into two reachability problems of $\leq 2^{m - 1}$ steps; recursion depth $m = O (f)$ , each level storing one midpoint of $O (f)$ bits, giving $O (f^{2})$ total work-tape space.

Reachability is in $NL = NSPACE (lo g n)$ , so $f = lo g n$ . Savitch gives $DSPACE ((lo g n)^{2}) = DSPACE (lo g^{2} n) .$ So the deterministic version of Reachability costs $O (lo g^{2} n)$ space — see Savitch's Theorem.

Level 4 — Synthesis

Exercise 4.1

Show SAT $\in NP$ and SAT $\in EXP$ , giving the resource bound for each, and say in one sentence what the gap between them illustrates.

Recall Solution

NP route (guess then verify): a formula on $n$ variables has a truth assignment describable in $n$ bits. Guess those $n$ bits nondeterministically, then evaluate the formula — plugging in values and checking each clause is $O (size) = poly (n)$ time. So SAT $\in NTIME (n^{k}) = NP$ .

EXP route (brute force): deterministically enumerate all $2^{n}$ assignments; evaluate each in poly time. Cost $2^{n} \cdot poly (n) = DTIME (2^{O (n)}) \subseteq EXP$ .

What the gap shows: checking a proposed solution is cheap (poly), while finding one is currently exponential — the beating heart of $P = ? NP$ . See NP-Completeness and Reductions.

Exercise 4.2

For $n = 20$ variables, compute the brute-force assignment count $2^{n}$ , and the certificate length in bits that the NP verifier reads. Contrast the two numbers.

Recall Solution

Brute-force assignments: $2^{20} = 1, 048, 576$ — over a million full evaluations.
NP certificate length: exactly $n = 20$ bits (one bit per variable), read once.

The verifier looks at 20 bits; the deterministic searcher may look at over a million assignments. That $20$ vs $1, 048, 576$ contrast is precisely why guessing well would be so powerful — and why we cannot currently do it deterministically in polynomial time.

Exercise 4.3

Order these classes into the full known chain and mark the two inclusions that are known to be strict: $P, NP, L, EXP, NL, PSPACE$ .

Recall Solution

$L \subseteq NL \subseteq P \subseteq NP \subseteq PSPACE \subseteq EXP .$ Known strict (via the Hierarchy Theorems):

$P ⊊ EXP$ — by the deterministic time hierarchy theorem: with $f$ time-constructible and $g lo g g = o (f)$ you get $DTIME (g) ⊊ DTIME (f)$ ; pick $g = n^{k}$ , $f = 2^{n}$ .
$NL ⊊ PSPACE$ — this one needs care: $NL = NSPACE (lo g n)$ is a nondeterministic space class, so separating it from $DSPACE (n^{k})$ uses the nondeterministic space hierarchy theorem (with the proper space-constructibility condition on the bounds), which gives $NSPACE (lo g n) ⊊ NSPACE (n) \subseteq DSPACE (n^{2}) \subseteq PSPACE$ (the middle step is Savitch). It is not just "the space hierarchy" applied naively — the nondeterministic version and constructibility are essential.

Every inclusion strictly between these (e.g. $P$ vs $NP$ , $L$ vs $NL$ ) is open. The rule: hierarchy theorems separate classes of the same type (D-time vs D-time, or N-space vs N-space), not $D$ vs $N$ of the same budget.

Level 5 — Mastery

Reminder for this level: $⟨ M ⟩$ denotes the encoding of machine $M$ as a finite string (its states and transitions spelled out), which any machine can take as input.

Exercise 5.1

Prove that $P \neq = EXP$ (i.e. the inclusion is strict) without citing the theorem name — reconstruct the diagonalization idea from scratch.

Recall Solution

The Time Hierarchy Theorem says: if $f$ grows enough faster than $g$ (precisely $g (n) lo g g (n) = o (f (n))$ ), then $DTIME (g) ⊊ DTIME (f)$ . Here is why, built from zero:

Simulate. With a time budget $f$ , build a universal machine $U$ that, given the code $⟨ M ⟩$ of any machine $M$ using only $g$ time, runs $M$ on its own code. The simulation overhead is a factor of about $lo g g$ , which the gap $g lo g g = o (f)$ absorbs — so $U$ finishes within $f$ .
Flip. Define a language $D$ : string $⟨ M ⟩$ is in $D$ iff $M$ (running in time $g$ ) rejects its own code. $D$ is decidable in $DTIME (f)$ (just simulate and flip the bit).
Contradiction. Suppose $D \in DTIME (g)$ , decided by some machine $M_{D}$ . Feed $M_{D}$ its own code $⟨ M_{D} ⟩$ . Then $⟨ M_{D} ⟩ \in D$ iff $M_{D}$ rejects $⟨ M_{D} ⟩$ iff $⟨ M_{D} ⟩ \in / D$ — a flat contradiction. So $D \in / DTIME (g)$ .

Thus $D \in DTIME (f) ∖ DTIME (g)$ : strictly more languages with more time. Choosing $g (n) = n^{k}$ (any polynomial) and $f (n) = 2^{n}$ (well inside $EXP$ ) satisfies the gap, so no polynomial time class captures $D$ , yet $EXP$ does. Therefore $P ⊊ EXP$ . This is the same self-referential move as the halting-problem argument in Decidability and the Halting Problem.

Exercise 5.2

Explain precisely why this diagonal argument proves $P \neq = EXP$ but fails to settle $P$ vs $NP$ .

Recall Solution

Diagonalization needs the bigger class to simulate every machine of the smaller class and then flip its answer, all within its own budget. This works when both classes measure the same resource (time vs time): more time can host the simulation-plus-flip.

For $P$ vs $NP$ the difference is not "more of the same resource" but a change of machine type ( $D$ vs $N$ ). A deterministic machine cannot cleanly "flip" a nondeterministic machine's answer, because $N$ -acceptance is an existential (accept if some branch accepts) — its negation is a universal, which is not the same machine model. So the diagonal trick does not transfer. Formally, results like the relativization barrier show diagonalization alone cannot resolve $P$ vs $NP$ . That is why one gap is a theorem and the other is a millennium prize.

Exercise 5.3

Steel-man and refute: "Because space is reusable and time is not, $DSPACE (f)$ must contain $DTIME (f)$ — memory is the cheaper, more powerful resource, so space classes are the small ones."

Recall Solution

The strong version of the claim: a single tape cell can be overwritten and reused across many steps, so a fixed amount of memory supports arbitrarily long computations. It genuinely feels like space is the "richer" resource.

Why it is exactly backwards for inclusions:

Reuse means space $\leq$ time (Ex 1.3 / Step 1): you can never touch more work cells than you have steps, so $DTIME (f) \subseteq DSPACE (f)$ — small time sits inside small space.
Reuse also makes space powerful in the other direction: bounded space $f$ permits up to $2^{O (f)}$ configurations (Ex 3.1), hence that much time — so $DSPACE (f) \subseteq DTIME (2^{O (f)})$ .

Combining: $PSPACE$ contains all of $NP$ and sits below $EXP$ — it is a huge class (a large outer ring in s01), not a small one. The reusability of memory is precisely what makes space classes large, so the claim's conclusion ("space classes are the small ones") is refuted by its own premise. See Space vs Time Tradeoffs.