Complexity — DTIME, DSPACE, complexity classes

1. WHY we measure as a function of input size

2. DTIME and DSPACE — the atomic building blocks

WHAT they are: sets of languages (decision problems), not single problems. WHY $O(\cdot)$ : by the linear speedup / tape-compression theorems, constant factors and finite tape-alphabet tricks can shrink time/space by any constant, so only the asymptotic class matters.

3. Building named classes from DTIME / DSPACE

4. Deriving the inclusion hierarchy from first principles

This is the part to derive, not memorize. We prove each step.

Worked example Step 2 —

$\mathrm{DSPACE}(f) \subseteq \mathrm{DTIME}(2^{O(f)})$ (for $f \ge \log n$ ) Why this step? Count the configurations. A configuration = (state, head position, tape contents over the $f(n)$ used cells). Number of them: $\#\text{configs} \le \underbrace{|Q|}_{\text{states}}\cdot \underbrace{f(n)}_{\text{head pos}}\cdot \underbrace{|\Gamma|^{f(n)}}_{\text{tape}} = 2^{O(f(n))}.$ A halting machine can never repeat a configuration (else it loops forever). So it runs at most $2^{O(f(n))}$ steps. Why this matters: bounded space forces bounded time.

Figure — Complexity — DTIME, DSPACE, complexity classes

5. The Hierarchy Theorems — why bigger budget = strictly more power

6. Worked examples

7. Common mistakes (Steel-manned)

8. Forecast-then-Verify

Recall Forecast before peeking

Q: Which is known strict: $\mathsf{P}$ vs $\mathsf{NP}$ , or $\mathsf{P}$ vs $\mathsf{EXP}$ ? Why?

A: $\mathsf{P}\subsetneq\mathsf{EXP}$ is known (Time Hierarchy: more time of the same kind via diagonalization). $\mathsf{P}$ vs $\mathsf{NP}$ is open because diagonalization compares the same resource at different budgets, but D-vs-N is a different kind of change — hierarchy theorems don't apply, and "relativization barriers" show simple diagonalization can't settle it.

9. Flashcards

What does

\mathrm{DTIME}(f(n))

contain?

All languages decided by some deterministic TM in

O(f(n))

steps (worst case).

Define

\mathsf{P}

in terms of DTIME.

\mathsf{P}=\bigcup_k \mathrm{DTIME}(n^k)

— polynomial deterministic time.

Why time

f \Rightarrow

space

\le f

The head moves

\le 1

cell per step, so in

f

steps it visits

\le f{+}1

cells.

Why does DSPACE

(f)\subseteq

DTIME

(2^{O(f)})

A halting machine can't repeat a configuration; there are only

2^{O(f)}

configurations.

State the standard inclusion chain.

\mathsf{L}\subseteq\mathsf{NL}\subseteq\mathsf{P}\subseteq\mathsf{NP}\subseteq\mathsf{PSPACE}\subseteq\mathsf{EXP}

What does NP stand for / mean?

Nondeterministic Polynomial time = solutions verifiable in poly time.

State Savitch's theorem.

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

, so

\mathsf{NPSPACE}=\mathsf{PSPACE}

Which separation is proved,

\mathsf{P}{\ne}\mathsf{EXP}

\mathsf{P}{\ne}\mathsf{NP}

\mathsf{P}\ne\mathsf{EXP}

(Time Hierarchy Theorem).

\mathsf{P}

\mathsf{NP}

is open.

Why is

\mathsf{P}

the "efficient" class?

Polynomials are closed under composition, so chaining efficient steps stays efficient.

Which complexity class is graph reachability complete for?

\mathsf{NL}

(guess the path one node at a time using

O(\log n)

space).

Why the

f\ge\log n

condition for space classes?

Below

\log n

you can't store a pointer into the input; needed for config counting.

Recall Feynman: explain to a 12-year-old

Imagine solving puzzles. Time is how many moves you make; space is how big a scratchpad you need. We sort puzzles into boxes by how many moves or how much paper they need. The "easy box" ( $\mathsf{P}$ ) holds puzzles where moves grow gently as the puzzle gets bigger — like $n^2$ , not $2^n$ . One neat trick: you can never scribble on more pieces of paper than the number of moves you make (each move touches at most one new spot). And if you only use a tiny notebook, you can't go on forever without repeating an exact notebook-state and looping — so a small notebook secretly limits how long you can run. Some boxes are provably bigger than others (more time really lets you solve more), but the most famous question — does guessing the answer help you find it faster ( $\mathsf{P}$ vs $\mathsf{NP}$ ) — nobody has solved yet.

Connections

Turing Machines — the model whose steps/cells we are counting.
NP-Completeness and Reductions — hardest problems inside $\mathsf{NP}$ ; defines the frontier.
Savitch's Theorem — collapses nondeterministic space.
Hierarchy Theorems — diagonalization proving strict separations.
Decidability and the Halting Problem — computability layer beneath complexity.
Big-O Asymptotic Notation — why constant factors vanish in these definitions.
Space vs Time Tradeoffs — engineering analogue of $\mathrm{DTIME}$ vs $\mathrm{DSPACE}$ .

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, complexity theory ka core idea simple hai: hum poochte hain "problem solve ho sakti hai?" (woh computability hai) aur uske baad "kya woh reasonable time aur memory me solve hogi?" — yahi complexity hai. Do main resources hain — time (kitne steps lagte hain) aur space (kitni tape ya memory chahiye). Inhe hum hamesha input size $n$ ke function ke roop me likhte hain, kyunki bada input matlab zyada kaam. $\mathrm{DTIME}(f)$ matlab "saari problems jo deterministic TM $O(f(n))$ steps me decide kar le", aur $\mathrm{DSPACE}(f)$ space ke liye same baat.

In choti bricks se badi classes bante hain: $\mathsf{P}=\bigcup_k \mathrm{DTIME}(n^k)$ — yani polynomial time, jise "efficient" maana jaata hai (kyunki polynomial ke andar polynomial daalo toh phir bhi polynomial rehta hai, robust hai). $\mathsf{NP}$ matlab guess-and-verify in polynomial time. Ek bahut zaroori derivation: head ek step me ek hi cell hilta hai, isliye time $f$ ka matlab space $\le f$ — yani $\mathsf{P}\subseteq\mathsf{PSPACE}$ . Aur agar space kam hai toh configurations bhi limited ( $2^{O(f)}$ ), aur halting machine koi configuration repeat nahi kar sakti, isliye time bhi $2^{O(f)}$ tak hi — bas isi se poori chain ban jaati hai: $\mathsf{L}\subseteq\mathsf{NL}\subseteq\mathsf{P}\subseteq\mathsf{NP}\subseteq\mathsf{PSPACE}\subseteq\mathsf{EXP}$ .

Yeh matter kyun karta hai? Kyunki interview aur GATE dono me yahi geography puchi jaati hai. Yaad rakho do galtiyan: (1) space time se chhota hota hai inclusion me, ulta nahi — reuse ke chakkar me confuse mat hona; (2) $\mathsf{P}\subseteq\mathsf{NP}$ toh pakka hai par strict hai ya nahi yeh aaj tak koi nahi jaanta — yahi famous $\mathsf{P}$ vs $\mathsf{NP}$ million-dollar sawaal hai. Lekin $\mathsf{P}\ne\mathsf{EXP}$ proved

Complexity — DTIME, DSPACE, complexity classes

1. WHY we measure as a function of input size

2. DTIME and DSPACE — the atomic building blocks

3. Building named classes from DTIME / DSPACE

4. Deriving the inclusion hierarchy from first principles

5. The Hierarchy Theorems — why bigger budget = strictly more power

6. Worked examples

7. Common mistakes (Steel-manned)

8. Forecast-then-Verify

9. Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Theory of Computation

Connections