We study decision problems — questions with a yes/no answer (e.g. "Does this graph have a route visiting all cities under length 100?"). We measure difficulty by how the running time grows with input size n.
Imagine a jigsaw puzzle. Checking if a finished puzzle is correct is easy — you just glance and see the picture. But solving it from a pile of pieces is hard work. "P" problems are like puzzles a robot can finish quickly. "NP" problems are like puzzles where, if someone shows you the finished picture, you can quickly say "yep, correct!" The giant mystery — P vs NP — is: for these check-easy puzzles, is there always a secret quick way to solve them too, or are some puzzles just doomed to be slow? Nobody on Earth knows. There's a million dollars waiting for whoever finds out.
Dekho, P vs NP ka core idea bahut simple hai: kya kisi answer ko dhoondhna utna hi aasaan hai jitna usko check karna? Maan lo koi tumhe bhara hua Sudoku de — tum jaldi se verify kar loge ki sahi hai ya nahi. Lekin khaali grid se solve karna? Bahut mehnat. Class P matlab woh problems jo poly time (n2, n3 type) me solve ho jaati hain. Class NP matlab woh problems jinka answer, agar koi hint (certificate) de de, toh poly time me verify ho jaata hai.
Ek galatfehmi door kar lo: NP ka matlab "Non-Polynomial" nahi hai. NP = Nondeterministic Polynomial = "verify karna easy". Isiliye har P problem NP me bhi hai (P⊆NP), kyunki agar tum solve kar sakte ho toh verify toh kar hi sakte ho. Asli sawaal ulta hai: kya P=NP? Yaani jo check-easy hai woh solve-easy bhi hai kya? Aaj tak kisi ko nahi pata — yeh ek open Millennium Problem hai, $1,000,000 inaam ke saath.
Yeh matter kyun karta hai? Agar kal koi prove kar de ki P=NP, toh RSA jaisi saari encryption tut jaaye, kyunki uski security isi baat par tiki hai ki factoring "find karna" mushkil hai. Saath hi logistics, scheduling, protein folding — sab fast solve ho jaaye. Aur ek key cheez: NP-complete problems (jaise SAT, Travelling Salesman) — agar inme se kisi ek ka bhi poly-time algorithm mil gaya, toh saari NP problems ek saath solve ho jaayengi. Isiliye yeh sab ek hi dhaage se bandhi hain.
Exam tip: yaad rakho "P = Promptly solve, NP = Notarize a proof". Aur brute force slow hone ka matlab yeh nahi ki problem P me nahi hai — best algorithm kuch aur ho sakta hai. Yeh chhoti-chhoti baatein steel-man karke samjho, tabhi concept pakka hoga.
