Intuition The ONE core ideaP is the collection of yes/no questions a normal computer can answer with a "steady-growing" amount of work — where "steady" means the number of steps stays below some fixed power of the input's written length (n 2 n 3
Before you can read "L ⊆ { 0 , 1 } ∗ P if M c ∣ x ∣ k assumed . We build them one at a time, each resting on the one before.
x x thing you hand to the computer : a finite row of symbols, like 10110 or PARIS. The parent writes x ∈ { 0 , 1 } ∗
{ 0 , 1 } 0 and the bit 1.The little star, { 0 , 1 } ∗ any finite sequence of those symbols== — length 0, 1, 2, … The star is read "Kleene star": zero or more, strung together .
∣ x ∣ n length
∣ x ∣ x n = ∣ x ∣ x = 10110, then ∣ x ∣ = n = 5
Why the topic needs this. Every timing claim in P is measured against n . The single most important trap on the parent page — "trial division looks fast but isn't" — is entirely about the difference between the value a string represents and the length n n
Common mistake Value vs. length — the trap you must feel nowThe number N = 1000000 value one million, but its length (in bits) is only n = ⌈ log 2 N ⌉ ≈ 20 always counted against the row's length n
Definition Decision problem and the symbolL decision problem is a question whose answer is always yes or no — e.g. "Is this number prime?"
We package it as a ==language L set of all inputs whose answer is YES .
"x ∈ L x in L x yes .
"x ∈ / L no .
So solving the problem = deciding membership in the set L
Intuition Why turn a question into a setA set is the cleanest mathematical object we have. "Does M M x ∈ L TIME complexity classes .
Why ⊆ The parent writes L ⊆ { 0 , 1 } ∗ ⊆ "is a subset of" — every member of the left is also a member of the right ==. It just says: L some collection of bit-strings (the yes-instances), sitting inside the pool of all bit-strings.
Definition The Turing machineM M Turing Machine ). Picture a long paper tape divided into cells, one symbol per cell, and a little head that can:
read the symbol under it,
write a new symbol,
move one cell left or right,
change its internal "state of mind."
One such read-write-move is called ==one step ==.
==Deterministic == means: given the current symbol and state, the next action is completely fixed — no coin flips, no guessing, no branching. Same input ⟶ same run, every time. (Contrast with NP — nondeterministic polynomial time , where guessing is allowed.)
M L M decides L x halts (stops, never loops forever) and outputs yes exactly when x ∈ L no otherwise.
Why the topic needs M "Fast enough to trust" is meaningless until we fix what a step is . The Turing machine gives us a countable unit of work. Thanks to the Cobham–Edmonds thesis , the number of steps is essentially the same (up to a polynomial factor) whether you use a TM, a RAM, or your laptop — so P doesn't depend on which machine you picture.
T ( n ) T ( n ) largest number of steps M n == (the worst case). It's a function: feed it a size n n n 2 T ( n ) ≈ n 2
Definition Big-O — the symbolO ( ⋅ ) O ( g ( n )) g "grows no faster than g == Formally T ( n ) = O ( g ( n )) c > 0 n 0 T ( n ) ≤ c g ( n ) n ≥ n 0 T g Time complexity & Big-O .
Why Big-O. We don't care whether a step takes 3 or 7 machine-cycles — that's a constant we can't control and it changes between computers. We care about the shape of the growth. Big-O throws away the constant and keeps the shape. That's exactly what makes P model-robust .
n polynomial == in n n 3 n 2 + 5 n + 7 top exponent k k = 2 O ( n k ) c ∣ x ∣ k c n k
Intuition Why the polynomial line, not some other linePolynomials are closed under composition : a polynomial of a polynomial is still a polynomial, ( n a ) b = n ab whole reason P is a stable, meaningful club — see Polynomial-time reductions where this closure does real work.
Now every symbol in the headline is earned. Read it slowly:
That single line now reads in plain English: "P is every yes/no problem a deterministic computer can settle in a number of steps bounded by a fixed power of the input's length."
Input string x over 0 and 1
Length n equals size of x
Deterministic Turing machine M
Running time T of n worst case
Read it bottom-up: strings give length; machine gives steps; steps + length give running time; Big-O shapes it; polynomial is the threshold — and languages decided that fast form P .
Self-test: can you answer each before revealing?
What does { 0 , 1 } ∗ Every finite string of 0s and 1s — "zero or more bits strung together" (Kleene star).
What is n = ∣ x ∣ The number of symbols in the input x length , not the value it represents.
What is a language L The set of all inputs whose answer is "yes"; solving the problem means deciding membership in L
What does x ∈ L That the correct answer for input x
What does "deterministic" mean for a Turing machine? The next action is completely fixed by the current symbol and state — no guessing or branching.
What is one "step"? A single read-write-move-and-change-state action of the machine's head.
What does "M L M x ∈ L
What is T ( n ) The worst-case number of steps over all inputs of length n
What does O ( g ( n )) T ( n ) ≤ c g ( n ) c n
Polynomial vs. exponential — where is n Polynomial has n base (n k n exponent (2 n
Why is P closed/robust? Because polynomials compose: a polynomial of a polynomial is still polynomial.
What does ⋃ k ≥ 1 TIME ( n k ) All languages decidable in O ( n k ) some constant exponent k
Parent: P — polynomial time Turing Machine Time complexity & Big-O TIME complexity classes Cobham–Edmonds thesis NP — nondeterministic polynomial time Polynomial-time reductions P vs NP problem NP-complete problems