P — polynomial time — Hinglish notes

4.6.22 · Coding › Theory of Computation

P KYA HAI?

Decision problems kyon? Theory of Computation sabse clean hoti hai yes/no answers ke saath (ek language mein membership). Zyada tar "find/optimize" problems ka ek equivalent decision version hota hai ("kya cost $\leq B$ ka koi solution hai?"), toh kuch miss nahi hota.

Turing machine kyon, aapka laptop kyon nahi? Kyunki Cobham–Edmonds thesis ki wajah se ("polynomial = feasible" thesis): koi bhi do reasonable deterministic models of computation ek doosre ko simulate kar sakte hain sirf polynomial overhead ke saath. Toh "kya yeh P mein hai?" ka same answer aata hai ek TM par, ek RAM par, aapke laptop par, ya ek multi-tape machine par. P model-robust hai — yahi poora reason hai ki yeh ek meaningful class hai.

POLYNOMIALS KYON? (asli wajah)

Growth compare karo (yahi iska core hai):

$n$	$n^{2}$	$n^{3}$	$2^{n}$
10	100	1 000	1 024
20	400	8 000	~ $1 0^{6}$
50	2 500	125 000	~ $1 0^{15}$
100	10 000	$1 0^{6}$	~ $1 0^{30}$

$n = 100$ par, cubic algorithm ek jhapki mein khatam hota hai; exponential wala universe ki age se bhi zyada time lega.

HUM KAISE DIKHATE HAIN KI EK PROBLEM P MEIN HAI? (bound derive karo)

Hum guess nahi karte — hum steps count karte hain aur prove karte hain ki count ek polynomial se bounded hai.

Yeh last example sabse important trap hai → mistakes dekho.

Common mistake Classic blunders ko steel-man karte hain

Mistake A: "Trial division poly hai, toh primality ka P mein hona obvious hai." Kyon sahi lagta hai: $N$ "chhota lagta hai." Sach: input size bits ki sankhya hai $n = lo g_{2} N$ , aur $N = 2^{n /2}$ , $n$ mein exponential hai. Fix: hamesha time ko input ki encoding length ke against measure karo, numeric value ke against nahi.

Mistake B: " $n^{100}$ P mein hai, toh P matlab practical." Kyon sahi lagta hai: "polynomial = fast" yeh slogan hai. Sach: $n^{100}$ P mein hai lekin practice mein bekar hai; P ek theoretical boundary of feasibility hai, aur yeh survive karta hai kyunki real-world poly algorithms ke exponents tend to karte hain chhote hone ke. Fix: P = "principle mein tractable," "guaranteed quick" nahi.

Mistake C: "Tiny $n$ ke liye $2^{n}$ theek hai, toh yeh basically poly hai." Kyon sahi lagta hai: chhote inputs explosion ko chhupaate hain. Fix: class membership sabhi bade $n$ ke liye asymptotic growth ke baare mein hai, ek ache case ke baare mein nahi.

Recall Feynman: 12-saal ke bacche ko samjhao

Lego bricks sort karne ki kalpana karo. Ek accha method: jab aapke paas double bricks hon, toh aap lagbhag chaar guna kaam karo — irritating, lekin kaam steadily badhta hai. Ek bura method: har extra brick time double kar deti hai, toh 60 bricks aapki poori zindagi se zyada time le leti. P un puzzles ki box hai jo aap ek acche, steadily-badhne wale method se solve kar sakte ho. Hum "kitni bricks" ko puzzle likhne mein kitna waqt lagta hai se measure karte hain, puzzle ki number-value se nahi — yehi woh sneaky part hai jo logo ko prime numbers ke baare mein fool karta hai.

Active Recall

Class P kya hai?

Decision problems jo ek deterministic Turing machine se polynomial time mein solvable hain,

⋃_{k} TIME (n^{k})

Time ko numeric value mein nahi balki input length (bits) mein kyon measure karte hain?

Kyunki

N

n = lo g_{2} N

bits mein encode kiya jaata hai, toh

N = 2^{n /2}

n

mein exponential hai; value use karne par exponential algorithms ko fast label kar dete.

"Polynomial time" ko feasibility ka chosen notion kyon banaya?

Polynomials composition ke under closed hain (poly ke andar poly = poly), P ko robust aur algorithms combine karne ke liye stable banata hai.

Cobham–Edmonds thesis kya hai?

Yeh claim ki polynomial-time = practically feasible, aur reasonable deterministic models ek doosre ko polynomial overhead ke saath simulate karte hain (toh P model-independent hai).

Kya PRIMES P mein hai, aur kis algorithm se?

Haan — AKS algorithm (2002) se, bits ki sankhya

n = lo g N

mein polynomial.

Kya graph reachability (s–t path) P mein hai?

Haan — BFS/DFS

O (V + E) \leq O (n^{2})

time mein chalta hai.

P complement ke under closed kyon hai?

Poly-time decider chalao aur yes/no answer flip karo — ek extra step, abhi bhi polynomial.

Kya

n^{100} \in P

ka matlab hai ki yeh practical hai?

Nahi — P ek theoretical feasibility boundary hai;

n^{100}

P mein hai lekin impractical hai.

Connections

NP — nondeterministic polynomial time
P vs NP problem
Polynomial-time reductions
NP-complete problems
Time complexity & Big-O
Turing Machine
Cobham–Edmonds thesis
TIME complexity classes