The asymmetry that defines NP: checking a witness is easy, finding one is (apparently) hard.
CLO-3 · Find vs verifyRound 2 · 30 ptsLecture 10
🔊 Listen
1 · Theory
A language L is in NP if there is a polynomial-time
verifierV such that
x ∈ L ⇔ ∃ certificate c, |c| ≤ poly(|x|), with V(x, c) accepting in poly(|x|) time.
Definition · NP via verifiers
SAT ∈ NP. Certificate: a satisfying assignment. Verifier: plug in, check each clause. Time: O(m) where m = clauses.
Solver (brute force): try all 2n assignments. Exponential.
The gap between O(m) and 2n is the P vs NP question: is there ever a polynomial-time algorithm
that finds the witness, not just checks it? Nobody knows. A million-dollar problem.
🔊 Listen
2 · The verifier picture · check vs find
The verifier doesn't have to find τ — it just checks whether someone's claim that τ works is correct. The "someone" is the existential quantifier in NP's definition. P = NP would mean there's a way to always find τ in polynomial time. P ≠ NP means there are problems where finding is fundamentally harder than checking.
Brute force: tries 2⁴ = 16 assignments. For each, checks all 3 clauses → 48 clause-evaluations total. With n = 30 this would be ~10⁹ clause-checks.
Verifier given τ = (1, 0, 1, 0): clause 1: x1=1 ✓ accept clause. clause 2: x2=0, x4=0, ¬x1=0 — all false → reject. The verifier rejects this τ in 9 work units. If asked again with τ = (0, 1, 0, 0), it accepts in 9 work units.
Asymmetry: the verifier always halts fast, regardless of n. The brute-force solver does too — but its running time is 2ⁿ, which becomes astronomical fast.
🔊 Listen
4 · Animated demo · auto-plays · loops
Same 3SAT instance · two algorithms race Auto-plays
Solver: brute force (2n)
Tested: 0
Verifier: given witness, check
Checks: 0
🔊 Listen
3 · Q&A defence notes
Q1. Why does the verifier finish in m steps, not 2n?
Because the verifier doesn't search — it is handed the satisfying assignment and just plugs it in. m clauses × O(1) literal-checks each = O(m). The certificate replaces the search.
Q2. What if the verifier is sometimes given a wrong certificate?
Then at least one clause evaluates to false and the verifier rejects. NP is one-sided: a yes-instance has SOME certificate that works; the verifier doesn't have to handle all possible certificates correctly, just identify the good ones.
Q3. Why is UNSAT (the complement of SAT) thought NOT to be in NP?
To certify "no assignment works", you'd have to rule out all 2n. There is no known polynomial-size certificate. UNSAT ∈ coNP. Whether NP = coNP is open.
Q4. Can the solver be smarter than brute force?
Yes — DPLL, CDCL, etc. all run faster in practice. But no algorithm is known whose worst-case runtime is polynomial. The asymptotic worst-case bound remains 2O(n).
Q5. Compare with PRIMES.
PRIMES was thought to be only in NP for decades. In 2002 (AKS) it was shown PRIMES ∈ P. So "in NP" doesn't mean "no polynomial algorithm exists" — only that one isn't obviously there.
🔊 Listen
6 · Pitfalls students stumble on
The certificate must be short. Polynomially short in |x|. If the certificate could be exponentially long, every language would trivially have a verifier — just hand it the answer table. The polynomial bound forces the witness to be structured.
Verifier ≠ decider. A verifier takes (input, certificate). A decider takes just (input). NP is defined via verifiers; P is defined via deciders. The certificate is the existential quantifier made explicit.
NP is a class of decision problems, not search problems. "Yes" instances are the ones with a witness. The verifier just confirms; it doesn't construct the witness or hand it back.
"NP" does not stand for "not polynomial." It stands for nondeterministic polynomial time. Every problem in P is also in NP — just ignore the certificate.