NP — non-deterministic polynomial, verifier definition

4.6.23 · Coding › Theory of Computation

NP KYA HAI?

Do equivalent views — dono NP hain, aur unhe equal prove karna ek standard exercise hai:

Verifier view (practical wala): "yes" instances ke paas ek short certificate hota hai jo ek fast checker accept karta hai.
Nondeterministic machine view (naam ki origin): ek nondeterministic Turing machine jo guess kar sakta hai aur polynomial time mein run karta hai, accept karta hai agar koi bhi computation branch accept kare.

DEFINITION AISA KYUN DIKHTA HAI? (First principles se derivation)

Hum "easy to check" ko formalize karna chahte hain. Raw idea se shuru karo aur har piece ko force karo:

Step 1 — Humein ek extra piece of information chahiye (certificate). Kyun? "Solution check karna" requires the solution to check. "Kya yeh graph 3-colorable hai?" ke liye, certificate ek coloring hai. $c$ ke bina tum wapas solving mein aa jaoge, checking mein nahi. Isliye hum $\exists c$ introduce karte hain.

Step 2 — Certificate short hona chahiye: $∣ c ∣ \leq p (∣ x ∣)$ . Kyun? Agar hum, say, exponential length ke certificates allow karte, toh verifier unhe polynomial time mein read bhi nahi kar paata, aur koi bhi problem trivially "qualify" kar leti. $∣ c ∣$ ko $∣ x ∣$ mein ek polynomial se bound karna proof ko reasonably sized rakhta hai.

Step 3 — Verifier $V$ polynomial time mein run karna chahiye. Kyun? "Easy to check" ka literally matlab fast hona chahiye. Polynomial time hamare "feasible" ka robust notion hai. Ek slow checker hard problems ko andar ghusne deta.

Step 4 — One-sided existence: sirf "yes" ko certificate chahiye. Kyun? $x \in L ⟺ \exists c (V (x, c) = 1)$ . "No" instances ke liye, koi bhi certificate kaam nahi karta — dikhane ke liye kuch nahi hai. Yahi asymmetry hai jiske wajah se NP aur co-NP alag maane jaate hain.

Steps 1–4 ko milana hi definition hai. Kuch assume nahi kiya gaya; har clause ek concrete loophole ka minimal fix hai.

PROVE KAISE KARO KI PROBLEM NP MEIN HAI (ek recipe)

$L \in$ NP show karne ke liye, teen questions ka jawab do:

Certificate kya hai? ("guessed" object)
Yeh polynomially short kyun hai? ( $∣ c ∣ \leq p (∣ x ∣)$ )
$V$ ise poly time mein kaise check karta hai?

Relationships jo tumhe pata hone chahiye

$P \subseteq NP$ (upar prove kiya).
$NP \subseteq EXP$ : length $\leq p (∣ x ∣)$ ke saare certificates brute-force karo; at most $2^{p (∣ x ∣)}$ hain, har ek poly time mein check hota hai $\Rightarrow$ overall exponential.
$P = NP$ hai ya nahi, yeh open hai (famous million-dollar question).

Common mistakes (Steel-manned)

Recall Feynman: 12-year-old ko explain karo

Ek treasure hunt imagine karo ek bade island par. Khazana dhundhna tumhe forever le sakta hai — millions of spots hain. Lekin agar tumhara dost bole "big oak tree ke neeche river ke paas khodo," toh tum wahan daud ke ja sakte ho aur paanch minute mein check kar sakte ho. NP problems woh treasure hunts hain jahan ek tip check karna quick hai, chahe scratch se search karna brutal ho. "Tip" hi certificate hai. NP promise nahi karta ki hunt fast hai — sirf ki answer verify karna easy hai.

Flashcards

NP literally kya stand karta hai?

Nondeterministic Polynomial time — NOT "non-polynomial."

NP ko verifiers ke through define karo.

L \in

NP iff ek poly-time verifier

V

aur polynomial

p

hai s.t.

x \in L ⟺ \exists c, ∣ c ∣ \leq p (∣ x ∣), V (x, c) = 1

Certificate/verifier ki teen properties kya honi chahiye?

Certificate polynomially short hai; verifier poly time mein run karta hai; certificate exist karta hai iff instance "yes" hai.

NP ki definition one-sided kyun hai?

Sirf "yes" instances ko certificate chahiye; "no" instances ke liye koi certificate

V

ko accept nahi karwa sakta (symmetric version co-NP hai).

SAT ke liye certificate?

Ek satisfying truth assignment; formula evaluate karke verify karo (poly time).

Hamiltonian Cycle ke liye certificate?

Saari vertices ka ek permutation; check karo ki har consecutive pair (aur wrap-around) ek edge hai aur saari vertices ek baar appear karti hain.

COMPOSITE ke liye certificate?

Ek nontrivial factor

d

1 < d < N

; verify karo

N mod d = 0

\subseteq

NP kyun hai?

Ek poly-time solver ek verifier ki tarah act karta hai jo certificate ignore karke problem re-solve karta hai.

\subseteq

EXP kyun hai?

Saare

\leq 2^{p (∣ x ∣)}

certificates brute-force karo, har ek ko poly time mein check karo.

Verifier aur nondeterministic-machine views kaise connect hote hain?

Nondeterministic guess written down hi certificate hai; guessing ke baad deterministic check hi verifier hai.

Kya "nondeterministic" aur "random" same hain?

Nahi — nondeterminism accept karta hai agar KOI branch accept kare (ek OR); randomness probabilities/majority use karta hai.

Connections

P (complexity class) — "solve fast" sibling; P $\subseteq$ NP.
co-NP — mirror class jisme "no" instances ke liye short certificates hote hain.
NP-Completeness — NP mein sabse hard problems Polynomial-Time Reductions ke through.
Cook–Levin Theorem — SAT NP-complete hai; is note ko verifier idea se jodta hai.
Nondeterministic Turing Machine — naam ke peeche ka machine model.
Boolean Satisfiability (SAT) — canonical NP example upar use kiya gaya.
P vs NP Problem — open question jiske around poori class orbits karti hai.