WHY decision problems? Theory of Computation is cleanest with yes/no answers (membership in a language). Most "find/optimize" problems have an equivalent decision version ("is there a solution of cost ≤B?"), so nothing is lost.
WHY a Turing machine and not your laptop? Because of the Cobham–Edmonds thesis (the "polynomial = feasible" thesis): any two reasonable deterministic models of computation simulate each other with only polynomial overhead. So "is it in P?" gives the same answer on a TM, a RAM, your laptop, or a multi-tape machine. P is model-robust — that's the whole reason it's a meaningful class.
We don't guess — we count steps and prove the count is bounded by a polynomial.
This last example is the most important trap → see mistakes.
Recall Feynman: explain it to a 12-year-old
Imagine sorting Lego bricks. A good method: when you have twice as many bricks, you do about four times the work — annoying, but the work grows steadily. A bad method: every extra brick doubles the time, so 60 bricks would take longer than your whole life. P is the box of puzzles you can solve with a good, steady-growing method. We measure "how many bricks" by how long it takes to write the puzzle down, not by the puzzle's number-value — that's the sneaky part that fools people about prime numbers.
Decision problems solvable by a deterministic Turing machine in polynomial time, ⋃kTIME(nk).
Why measure time in input length (bits) not numeric value?
Because N encoded in n=log2N bits means N=2n/2 is exponential in n; using value would mislabel exponential algorithms as fast.
Why is "polynomial time" the chosen notion of feasibility?
Polynomials are closed under composition (poly inside poly = poly), making P robust and stable for combining algorithms.
What is the Cobham–Edmonds thesis?
The claim that polynomial-time = practically feasible, and reasonable deterministic models simulate each other with polynomial overhead (so P is model-independent).
Is PRIMES in P, and by what algorithm?
Yes — by the AKS algorithm (2002), polynomial in the number of bits n=logN.
Is graph reachability (s–t path) in P?
Yes — BFS/DFS runs in O(V+E)≤O(n2) time.
Why is P closed under complement?
Run the poly-time decider and flip the yes/no answer — one extra step, still polynomial.
Does n100∈P mean it's practical?
No — P is a theoretical feasibility boundary; n100 is in P but impractical.
Dekho, P ka matlab hai un saare yes/no problems ka group jinhe ek normal (deterministic) computer polynomial time mein solve kar sakta hai — yaani steps ki sankhya n2, n3 jaise badhti hai, na ki 2n jaise phategi. Yahan n hai input ka size (jaise kitne bits ya kitne vertices). Idea simple hai: polynomial waale algorithms scale karte hue bhi sambhal jaate hain, lekin exponential waale chhote input pe bhi zindagi nikaal dete hain.
Sabse important baat — aur yahin students galti karte hain — time ko input ki length (bits) ke against naapo, number ki value ke against nahi. Jaise primality check: trial division N steps leta hai, lagता hai chhota hai, par input size n=log2N bits hai, aur N=2n/2 — yeh to exponential nikla! Isliye trial division se PRIMES ∈ P prove nahi hota. Asli jugaad AKS algorithm (2002) se aata hai jo bits mein polynomial hai.
P itni khaas isliye hai kyunki yeh robust hai — chahe Turing machine ho, ya tumhara laptop, ya RAM model, sab ek doosre ko sirf polynomial overhead mein simulate kar lete hain (Cobham–Edmonds thesis). Aur polynomials compose hote hain: poly ke andar poly daalo, phir bhi poly. Isi wajah se hum P ko "practically solvable" maante hain. Yaad rakho mantra: "Bits, not value" aur "Patient but Possible".
