Complexity — DTIME, DSPACE, complexity classes: Question bank

Before the questions, one tiny glossary so no symbol is unearned:

True or false — justify

A configuration means (state, head position, tape contents). Keep that in mind — several answers count them.

P \subseteq PSPACE

True. In

f (n)

steps the head moves at most one cell per step, so it touches at most

f (n) + 1

cells — you can never use more space than time (Step 1).

PSPACE \subseteq P

False (and believed strict the other way). Space is reusable, so

DSPACE (f)

can run for up to

2^{O (f)}

steps before repeating a configuration — polynomial space buys exponential time, not the reverse.

P ⊊ NP

is a proven theorem.

False. Only

P \subseteq NP

is proven (a deterministic machine is a trivial nondeterministic one). Whether it is strict is the open

P = ? NP

problem.

P ⊊ EXP

is a proven theorem.

True. The time hierarchy theorem separates them by diagonalization — with exponential time you simulate every polynomial-time machine and flip its answer, producing a language no polynomial machine decides.

NL \subseteq P

True. A logspace machine has only polynomially many configurations, so you build its configuration graph and search it in polynomial time.

NPSPACE = PSPACE

True, by Savitch's Theorem:

NSPACE (f) \subseteq DSPACE (f^{2})

, and squaring a polynomial is still polynomial, so nondeterminism gives no extra space power at the polynomial level.

NL = L

is settled.

False — it is open. Savitch only gives

NL \subseteq DSPACE (lo g^{2} n)

, which is bigger than

L = DSPACE (lo g n)

, so it does not collapse them.

DTIME (n^{2}) \subseteq DTIME (n^{3})

True, and in fact strict by the time hierarchy theorem since

n^{2} lo g n = o (n^{3})

. More time budget genuinely decides more languages.

L \in DTIME (n)

then

L \in P

True.

P = ⋃_{k} DTIME (n^{k})

, and linear is the

k = 1

case, which sits inside the union.

Constant factors matter when classifying a language into

DTIME

False. The linear-speedup / tape-compression theorems let you shrink time and space by any constant, which is exactly why the definitions use

O (\cdot)

Every language is in some

DTIME (f)

False. Only decidable languages have a halting machine; undecidable ones (like the halting problem, see Decidability and the Halting Problem) sit outside every

DTIME

class.

Spot the error

"Space is reusable, so

DSPACE (f) \subseteq DTIME (f)

Backwards. Reuse means you use few cells but possibly many steps; the correct bound is

DSPACE (f) \subseteq DTIME (2^{O (f)})

(for

f \geq lo g n

) by counting non-repeating configurations.

"NP stands for Non-Polynomial."

No — NP = Nondeterministic Polynomial time. It contains all of

P

, so it certainly contains polynomial-time problems; the name refers to the machine model, not to ruling out polynomial time.

DTIME (2^{n}) = EXP

EXP = ⋃_{k} DTIME (2^{n^{k}})

is a union over all constant

k

, strictly larger than the single class

DTIME (2^{n})

(which is

k = 1

"A halting machine can revisit a configuration to save time."

If a deterministic machine ever repeats a configuration it would loop forever and never halt — so a halting machine visits each configuration at most once, which is exactly what bounds its running time.

"Savitch's Theorem gives

NTIME (f) \subseteq DTIME (f^{2})

Savitch is about space, not time:

NSPACE (f) \subseteq DSPACE (f^{2})

. No such cheap squaring is known for nondeterministic time — that would essentially settle

P

NP

L = DSPACE (lo g n)

can't even store the input, so it's useless."

The

lo g n

counts work-tape cells; the read-only input tape is not charged. A logspace machine still reads all

n

symbols — it just can't copy them into working memory, only keep

O (lo g n)

-bit pointers/counters.

T (n) = max {t_{M} (w) : ∣ w ∣ = n}

measures the average case."

The

max

makes it the worst case — the single hardest input of that length — not the average.

Why questions

Why is

P

chosen as the line between "tractable" and "intractable" rather than, say,

DTIME (n^{2})

Because polynomials are closed under composition — a polynomial of a polynomial is polynomial — so chaining efficient subroutines stays efficient. Fixed-degree classes lack this robustness.

Why does bounded space force bounded time, but not the reverse?

Bounded space means finitely many configurations, and a halting machine cannot repeat one, so time is capped. Bounded time already caps space (Step 1), but low space still allows exponentially long non-repeating runs.

Why is

P \neq = EXP

known while

P \neq = NP

is not?

The hierarchy theorems separate classes of the same resource type (D-time vs D-time) via diagonalization.

P

NP

compares different models (D vs N) at the same budget, where the flip-your-own-answer trick doesn't directly apply.

Why do we measure cost as a function

f (n)

instead of a single number?

A single number ("40 ms") is meaningless without input size;

f (n)

covers inputs of every size at once and exposes the growth rate, which dominates as inputs scale.

Why does verifying SAT being easy while solving it seems hard capture the heart of

P

NP

NP is exactly "problems whose solutions are cheap to check". Whether cheap checking implies cheap finding for every such problem is precisely

P = ? NP

Why does the configuration count give

∣ Q ∣ \cdot f (n) \cdot ∣Γ ∣^{f (n)}

A configuration is fully described by the state (

∣ Q ∣

choices), the head position among the

f (n)

used cells, and the contents of those cells (each of

∣Γ∣

symbols, so

∣Γ ∣^{f (n)}

Why does Savitch cost

O (f^{2})

space and not more?

Reachability in

\leq 2^{k}

steps splits at a midpoint into two half-length reachability problems, giving recursion depth

lo g (2^{O (f)}) = O (f)

; each level stores one

O (f)

-bit configuration, so

O (f) \times O (f) = O (f^{2})

Edge cases

Where does the bound

DSPACE (f) \subseteq DTIME (2^{O (f)})

need the extra hypothesis

f \geq lo g n

You need at least

lo g n

space just to write down a head position on an

n

-cell input; below that the configuration-counting argument (which uses

f (n)

for the head-position factor) doesn't cleanly hold.

What happens to the class hierarchy if the input has length

n = 0

(empty string)?

The machine still has finitely many configurations and either accepts or rejects immediately;

ε

is a single fixed input, so it never affects asymptotic class membership, which is about behaviour as

n \to \infty

DTIME (1)

(constant time) meaningful for a Turing machine?

Barely — in

O (1)

steps the single-tape head can't even scan the whole input, so it decides only trivial languages depending on a bounded prefix. Real classification starts at

DTIME (n)

, enough to read the input once.

Does

NL \subseteq P

contradict

NL

using only

lo g n

space?

No. Log space means poly-many configurations (

2^{O (l o g n)} = n^{O (1)}

), and searching that polynomial-size graph takes polynomial time — small space, larger (but still polynomial) time.

For the reachability problem in

NL

, what is stored when the graph has no

s

–

t

path at all?

The machine still only ever holds the current node and a step counter (

O (lo g n)

bits each); after

n

guesses without reaching

t

it rejects. It never stores the path, so space stays logarithmic regardless of the answer.

If a "machine" never halts on some inputs, can its language be placed in a

DTIME

class?

Not via that machine —

DTIME

requires a machine that halts on all inputs. A non-halting machine has undefined worst-case time and cannot certify class membership.

Is the empty language

\emptyset

L

P

, and

PSPACE

Yes — a machine that rejects everything uses

O (1)

space and

O (n)

time (just to halt), so

\emptyset

sits in the smallest classes and therefore in all the larger ones by inclusion.

Recall Quick self-test

One-word resource that space classes bound but which stays reusable ::: space (cells can be overwritten) The proof technique behind every hierarchy theorem ::: diagonalization (simulate then flip) The theorem making nondeterministic space cheap to determinize ::: Savitch's ( $f \to f^{2}$ )