Intuition The one core ideaA complexity class is a bucket that holds every decision problem you can solve inside a fixed budget of time (steps) or space (memory cells), written as a function of the input's length. Everything in this topic is about measuring those two budgets, naming the buckets, and proving which bucket sits inside which.
Before you can read the parent note, you need to be able to look at each squiggle — n O ( ⋅ ) DTIME ⊆ 2 O ( f ) see what it means. This page builds every one of them from nothing. We go strictly in order: each symbol only uses symbols already defined above it.
Everything here is measured on a Turing machine (TM). You do not need its full theory — just this picture.
Definition A Turing machine, in one pictureImagine an infinite paper tape divided into cells. A little head sits over one cell. It can read the symbol there, overwrite it, and slide one cell left or right per step . A tiny controller (a finite list of rules) decides what to do based on (current rule-state, symbol under head).
The two things we will count are drawn right there:
how many steps the head takes before it stops → this becomes time ,
how many distinct cells the head ever touches → this becomes space .
Intuition Why a TM and not a real laptop?We want a definition of "steps" and "memory" that does not depend on brand of CPU. The TM is the simplest fully-specified machine where "one step" and "one cell" are unambiguous. Any reasonable computer differs from it by only a polynomial factor, which (we'll see) does not change the buckets.
w n = ∣ w ∣ string w 10110 or abba. Its length is the number of symbols in it, written ∣ w ∣ n n = ∣ w ∣. ∣ ⋯ ∣
Intuition Why measure everything againstn function of n — one formula that works for inputs of every size. That is the whole reason the parent writes T ( n ) S ( n )
A language L set of strings — the collection of all inputs whose answer is "YES". "Deciding L w w ∈ L w ∈ / L
The symbol ∈ ∈ /
Worked example Concrete languageLet L pal w abba ∈ L pal abc ∈ / L pal L pal
Intuition Why languages, not "problems"Every yes/no question ("is this graph connected?", "is this formula satisfiable?") becomes: which strings encode a YES instance? Turning problems into sets of strings lets one clean definition — the language — cover them all. This is why the parent says a complexity class is a set of languages , i.e. a set of sets of strings.
We count on a deterministic machine M halts (stops) on every input.
t M ( w ) steps M w s M ( w ) distinct cells M w
For each input length n worst (largest) one:
T ( n ) = max { t M ( w ) : ∣ w ∣ = n } , S ( n ) = max { s M ( w ) : ∣ w ∣ = n } .
The symbol max { … } : reads "such that". So T ( n ) n
We want a guarantee . If we promise "at most T ( n ) any length-n
g ( n ) = O ( f ( n )) g at most a constant multiple of f c > 0 n 0 g ( n ) ≤ c ⋅ f ( n ) n ≥ n 0
Picture two curves: g under a stretched copy c ⋅ f n growth rate . Deeper treatment: Big-O Asymptotic Notation .
needs O ( ⋅ ) linear-speedup and tape-compression theorems, you can shave time or space by any constant just with hardware tricks (bigger alphabet, more tapes). So constants are not a real property of the problem . Wrapping everything in O ( ⋅ ) O
O ( n 2 ) n 2 Why it feels right: we casually say "it's O ( n 2 ) Fix: O ( n 2 ) upper-bound family — it includes 3 n 2 + 5 n n 2 n log n n 2
N f : N → N N = { 0 , 1 , 2 , 3 , … } f : N → N f f ( n ) = n 2 f ( n ) = 2 n f budget : "you may use up to f ( n )
function is the budget
The budget must scale with input size (bigger input, bigger allowance). So the budget itself is a function of n f ( n ) = n 2 f ( n ) = 2 n
Everything above was scaffolding. Here is the payoff.
Decode it left to right with the symbols you now own:
{ L : … } L ∃ deterministic ("D") — the machine's next move is fully forced; no choices. (Swap in "N" for nondeterministic and you get NTIME NSPACE guess , covered in NP-Completeness and Reductions .)O ( f ( n ))
So DTIME ( n 2 ) the bucket of all yes/no problems some ordinary machine can solve in at-most-quadratic time .
Recall What does the "D" stand for, and what changes if it becomes "N"?D = deterministic (moves forced). N = nondeterministic — the machine may guess/branch; you only need one branch to accept. ::: D means one forced path; N lets the machine explore many paths and accept if any succeeds.
The named classes are built by plugging specific f
Definition Three growth shapes
n k polynomial : n , n 2 , n 3 , … k P 2 n exponential : doubles each time n EXP log n logarithmic : the inverse of 2 n log 2 1000 ≈ 10 n L
log n n log 2 n i 0 ≤ i < n O ( log n ) L Space vs Time Tradeoffs .
⋃ k ≥ 1 ⋃ ⋃ k ≥ 1 DTIME ( n k ) DTIME ( n 1 ) DTIME ( n 2 ) DTIME ( n 3 )
Intuition Why a union, not a singlek n 2 n 7 all of them, so we union over every exponent k P = ⋃ k ≥ 1 DTIME ( n k )
Definition Two arrows of inclusion
A ⊆ B A B A B B A ⊊ B A strictly inside B A ⊆ B and B A
Intuition Why the distinction is the whole dramaThe parent's chain P ⊆ NP ⊆ PSPACE ⊆ prove each fits inside the next. Turning any of those ⊆ ⊊ P NP Hierarchy Theorems are exactly the tools that upgrade some ⊆ ⊊ Savitch's Theorem collapses some the other way (NPSPACE = PSPACE
P ⊆ NP P ⊊ NP Why it feels right: guessing seems strictly stronger. Fix: ⊆ strictness (⊊ ⊊
2 O ( f ( n )) O ( f ( n )) f 2 that 2 O ( f ) 2 c ⋅ f ( n ) f 2 O ( f )
Intuition Why this exact shape appearsCount the distinct snapshots (state + head position + tape contents) of a machine limited to f ∣ Q ∣ ⋅ f ( n ) ⋅ ∣Γ ∣ f ( n ) = 2 O ( f ( n )) DSPACE ( f ) ⊆ DTIME ( 2 O ( f ) ) Decidability and the Halting Problem .)
Turing machine steps and cells
Input string w and length n
Language a set of strings
Complexity class a bucket of languages
Named classes P NP L PSPACE EXP
Inclusions subseteq and subsetneq
2 to the O of f snapshots
Cover the right side; if you can answer each, you're ready for the parent note.
What does n n = ∣ w ∣ w
What is a "language" in this subject? A set of strings — exactly the inputs whose answer is YES.
Why is cost written as a function of n Programs slow down on bigger inputs, so we need one formula covering every input size and comparing growth rates.
What does T ( n ) = max { t M ( w ) : ∣ w ∣ = n } The largest step-count over all inputs of length exactly n
What does g ( n ) = O ( f ( n )) There exist c > 0 n 0 g ( n ) ≤ c ⋅ f ( n ) n ≥ n 0 g f
Why do the DTIME/DSPACE definitions wrap the budget in O ( ⋅ ) Speedup/compression theorems remove constant factors, so only the asymptotic growth is a real property of the problem.
What does the "D" in DTIME mean, and its "N" cousin? D = deterministic (moves forced); N = nondeterministic (machine may guess/branch, accepts if any branch does).
How many bits store a counter up to n About log 2 n L = DSPACE ( log n )
Why is P ⋃ k ≥ 1 DTIME ( n k ) Different problems need different polynomial degrees, so we union over all exponents k
Difference between A ⊆ B A ⊊ B ⊆ A B ⊊ B A
Where does 2 O ( f ) It's the number of distinct machine configurations using f
