P vs NP — statement, why it matters: Worked examples

This page is the "try every case" companion to the P vs NP topic note. We will not add new theory — we will take the ideas ( $P$ , $N P$ , verifier, certificate, NP-complete) and push them through every kind of situation you can meet, including the weird edge cases and the exam trick questions.

Before we start, one reminder in plain words so nothing is used before it's built:

Recall The four words we keep using

Decision problem ::: a question with a yes / no answer. $P$ ::: problems a computer can solve (find the yes/no) in time $O (n^{k})$ — polynomial, "fast". $N P$ ::: problems where, if the answer is yes, someone can hand you a short certificate and you can check it's really yes in polynomial time. Certificate (witness) ::: the short "hint" (like a filled-in Sudoku) that a checker verifies.

The scenario matrix

Think of every P vs NP question as landing in exactly one of these cells. Our examples below will visit each one.

Cell	Situation	The trap it hides
C1	Problem is in P (solve fast)	Beginners forget it's also in NP
C2	Problem is in NP but its P-status is open / NP-complete	"verifiable" ≠ "solvable"
C3	NP-hard but NOT in NP (degenerate / undecidable)	the name "NP-hard" fools you
C4	The "no" answer — can we certify a no?	NP only promises a yes-certificate
C5	Zero / degenerate input ( $n = 0$ , empty set, trivial target)	edge cases break naive reasoning
C6	Limiting behaviour: exponential $2^{n}$ vs polynomial $n^{k}$ as $n \to \infty$	"finite" is mistaken for "fast"
C7	Word problem (real world)	translating English → decision problem
C8	Exam twist: "one NP-complete problem is in P"	the collapse $P = N P$

Now, one figure to fix the whole landscape in your eyes before the examples.

Figure — P vs NP — statement, why it matters

Example 1 — Cell C1 (a problem that IS in P, and therefore in NP)

Worked example Is "Is

$x$ present in a sorted list?" in $P$ ? in $N P$ ? Forecast: guess now — is this one fast? and is it also verifiable?

Model it. Input = a sorted array of $n$ numbers plus a target $x$ ; output = yes if $x$ appears. Why this step? Every analysis begins by naming the input size $n$ and the yes/no question.
Solve it. Binary search: check the middle, throw away half each time. Steps $\approx lo g_{2} n$ . Why this step? $lo g_{2} n$ is far smaller than any $n^{k}$ , so it fits $O (n^{k})$ → it's in $P$.
Is it in $N P$ ? Yes — build a verifier that ignores the certificate and just runs binary search itself. Why this step? This is exactly the $P \subseteq N P$ argument: a solver is a (certificate-ignoring) verifier.

Verify: for $n = 1, 000, 000$ , binary search needs $⌈ lo g_{2} n ⌉ = 20$ comparisons — genuinely instant. And since it's in $P$ , it is automatically in $N P$ . ✔

Example 2 — Cell C2 (in $N P$ , P-status open: Subset-Sum)

Worked example Given integers

$S = {3, 34, 4, 12, 5, 2}$ and target $t = 9$ , is there a subset summing to $9$ ? Is this in $N P$ ? Forecast: try to find the subset in your head first — how long did it take vs how long to check?

The certificate. A candidate subset, e.g. ${4, 5}$ . Why this step? $N P$ needs a short hint a prover could hand us.
The check. Add the chosen numbers: $4 + 5 = 9 = t$ . That's $O (n)$ additions. Why this step? Verification must run in polynomial time; addition of $n$ numbers is linear. ✔ in $N P$ .
Solving vs checking. Finding a subset in general may need trying up to $2^{n}$ subsets — this is the NP-complete part; nobody knows a poly-time solver. Why this step? This is the whole drama of P vs NP: verify = easy, find = maybe-hard.

Verify: $4 + 5 = 9$ ✔. Also ${3, 4, 2} = 9$ works. Both certificates pass the $O (n)$ checker, confirming membership in $N P$ . The existence of a fast solver is open. ✔

Example 3 — Cell C4 (certifying a "NO" answer — the subtle case)

Worked example For Subset-Sum on

$S = {2, 4, 6}$ , target $t = 5$ : the answer is NO. Does $N P$ give us a short certificate for "no"? Forecast: guess — can you quickly prove to a friend that NO subset sums to 5?

List the reality. All subset sums of ${2, 4, 6}$ are even: $0, 2, 4, 6, 8, 10, 12$ . Never $5$ . Why this step? We first confirm the answer really is "no".
Ask what $N P$ promised. $N P$ guarantees a short certificate only for yes-instances. For a "no", there's no promised short hint. Why this step? This is the exact asymmetry students miss — $N P$ is one-sided.
Where "no" lives. Certifying "no" cheaply is the job of the class co- $N P$ ; whether $N P = co- N P$ is another open problem. Why this step? It shows the matrix has a whole side (the "no" side) the beginner never sees.

Verify: every subset sum of ${2, 4, 6}$ is even (sum of even numbers is even), and $5$ is odd, so no subset gives $5$ . The answer is a genuine "no", with no $N P$ -style short certificate promised. ✔

Example 4 — Cell C6 (limiting behaviour: why "finite" ≠ "fast")

Worked example TSP-decision: is there a tour of

$n = 20$ cities of length $\leq L$ ? Brute force tries all orderings. Is "finite time" enough to be in $P$ ? Forecast: brute force always finishes — does that make it polynomial?

Count brute-force work. Number of orderings $\approx n! = 20!$ . Why this step? We must compare growth rate, not just finiteness.
Put a number on it. $20! \approx 2.43 \times 1 0^{18}$ . At a billion tours/second, that's about $77$ years. Why this step? To feel that "finite" can still be humanly impossible.
Compare with polynomial. A hypothetical $n^{3}$ solver at $n = 20$ is $8, 000$ steps — microseconds. Why this step? $P$ demands polynomial, and $n!$ crushes any $n^{k}$ as $n \to \infty$ .
But verifying is easy. Given a tour, sum its $n$ edge lengths, compare to $L$ : $O (n)$ → in $N P$ . ✔

Verify: $20! = 2432902008176640000 \approx 2.43 \times 1 0^{18}$ ; at $1 0^{9}$ /s that's $2.43 \times 1 0^{9}$ s $\approx 77$ years. Meanwhile $2 0^{3} = 8000$ . Finite ≠ fast. ✔

Example 5 — Cell C5 (zero / degenerate inputs)

Example 6 — Cell C3 (NP-hard but NOT in NP — the Halting Problem)

Worked example Is the

Halting Problem in $N P$ ? Is it NP-hard? Forecast: the name "NP-hard" — does it force a problem to sit inside $N P$ ?

Recall Halting. "Does program $M$ halt on input $w$ ?" It is undecidable — no algorithm decides it at all, at any speed. Why this step? If we can't even decide it in finite time, we surely can't verify every yes-instance in polynomial time.
So it's NOT in $N P$ . $N P$ requires a poly-time verifier; an undecidable problem has none. Why this step? Kills the assumption "NP-hard ⇒ in NP".
Yet it IS NP-hard. Every $N P$ problem reduces to it (it's at least as hard as all of $N P$ — in fact harder). Why this step? NP-hard = "at least as hard as all of NP", which allows harder problems.

Verify (logic): NP-complete $=$ NP-hard $\cap$ $N P$ . Halting is NP-hard but $\in / N P$ , so Halting is NP-hard, not NP-complete. This is exactly cell C3. ✔

Example 7 — Cell C7 (real-world word problem)

Worked example A delivery company must load a van (capacity 50 kg) from parcels weighing

${20, 15, 25, 10, 30}$ kg. "Can we load parcels totalling exactly 50 kg?" Classify this problem. Forecast: which class — and can you find the load faster than you can check it?

Translate to a decision problem. This IS Subset-Sum: set $= {20, 15, 25, 10, 30}$ , target $t = 50$ . Why this step? Real problems must be mapped to a known formal problem before classifying.
Provide a certificate. Try ${20, 30}$ : $20 + 30 = 50$ . ✔ Why this step? A certificate proves the yes-instance and shows it's in $N P$ .
Classify. Subset-Sum is NP-complete → in $N P$ , and no known poly-time solver. Why this step? Connects the concrete van to the abstract class (cell C2/C7).

Verify: $20 + 30 = 50$ ✔; also $15 + 25 + 10 = 50$ ✔. Two valid certificates, both check in $O (n)$ . In $N P$ ; solving in general is the hard part. ✔

Example 8 — Cell C8 (exam twist: the collapse)

Worked example Exam claim: "A student proves

SAT has an $O (n^{5})$ algorithm. Therefore Travelling-Salesman-decision is also in $P$ ." True or false — and why? Forecast: does one poly-time NP-complete algorithm really drag everything down with it?

Recall Cook–Levin. SAT is NP-complete — every $N P$ problem reduces to SAT in poly time. Why this step? NP-completeness means SAT is a "master key" for all of $N P$ .
Chain the reductions. TSP-decision is in $N P$ → reduces to SAT in poly time. If SAT $\in P$ , run: reduce (poly) then solve SAT ( $O (n^{5})$ ). The composition is still polynomial. Why this step? Polynomial ∘ polynomial = polynomial, so TSP-decision would be in $P$ too.
Conclude. So the claim is TRUE: one poly-time NP-complete algorithm ⇒ $P = N P$ , and all of $N P$ collapses into $P$ . Why this step? This is precisely the "they all stand or fall together" statement, made concrete.

Verify (logic): SAT NP-complete + SAT $\in P$ $\Rightarrow$ $N P \subseteq P$ ; with $P \subseteq N P$ always true, we get $P = N P$ . TSP-decision $\in N P \subseteq P$ . Claim holds. ✔

Connections

Parent: P vs NP statement
NP-Completeness and Reductions
Cook–Levin Theorem
SAT and Boolean Satisfiability
Big-O and Time Complexity
Decision Problems and Languages
Turing Machines (Deterministic vs Nondeterministic)
Halting Problem (undecidability)
Cryptography and RSA