Exercises — P vs NP — statement, why it matters

(a) True — a solver can ignore the certificate and just solve, so it doubles as a verifier. (b) False — NP = Nondeterministic Polynomial; it is about verifying, not slowness. (c) True — this is exactly (a) restated: $P\subseteq NP$. (d) False — it is open; experts believe $P\ne NP$ but nobody has a proof. Score: 4 correct = full marks.

• Certificate (the hint): (i) filled grid, (iii) the subset.
• Verifier (the poly-time checker): (ii) the validity scan, (iv) the addition-and-compare. Rule of thumb: a certificate is a thing handed to you; a verifier is an algorithm you run on it.

Follow the verifier recipe.

1. Certificate: the list of $k$ vertices claimed to form the clique. Why: it is the natural "hint" a prover supplies. Each vertex is named by an ID, and there are $n$ vertices, so an ID costs about ${\log }_{2}n$ bits; the whole certificate has size $O(k\log n)$ — still polynomial in the input size.
2. Verifier $V(G,k,c)$: (a) check $c$ has exactly $k$ distinct vertices; (b) check all $\left(\genfrac{}{}{0ex}{}{k}{2}\right)$ pairs are edges of $G$.
3. Time: checking all pairs is at most $\left(\genfrac{}{}{0ex}{}{k}{2}\right)\le \frac{n^2}{2}=O(n^2)$ — polynomial. ✔
4. Correctness: if a $k$-clique exists, the certificate listing it passes; if none exists, no set of $k$ vertices is fully connected, so nothing passes. Therefore CLIQUE $\in NP$. (Whether it's also in $P$ is unknown — but we will not use any hardness claim here; membership in NP is all this exercise asks for.)

$20!\approx 2.43\times 10^{18}$ orderings. Time $=\frac{2.43\times 10^{18}}{10^9}=2.43\times 10^9$ seconds. Convert: one year $\approx 3.15\times 10^7$ s, so $\frac{2.43\times 10^9}{3.15\times 10^7}\approx 77\text{ years}.$ The figure below drives the point home. Its amber curve is $n!$: read off the marked dot at $n=20$, which sits near $10^{18}$ — the value we just computed. Compare it with the cyan curve $n^3$ (a stand-in for a "polynomial / P-world" cost) and the dashed white curve $2^n$. Even on a logarithmic vertical axis (each gridline is $\times 10$), the amber factorial climbs almost vertically while the cyan polynomial stays low and flat. That visual gap is the whole lesson: "finite" is not "polynomial" — factorial growth crushes any real machine long before the polynomial curve breaks a sweat.

Let $L\in P$, so there is a deterministic solver $A$ running in $O(n^k)$ that outputs yes/no correctly. Construct a verifier $V(x,c):=A(x)$ — it throws the certificate $c$ away and just runs $A$.

• Poly time: $V$ runs in the same $O(n^k)$ as $A$ (ignoring $c$ costs nothing).
• Yes-instance: if $x$ is a yes, then $A(x)=\text{yes}$, so every $c$ (in particular a short one) passes — "some $c$ passes" holds.
• No-instance: if $x$ is a no, then $A(x)=\text{no}$, so no $c$ passes — the verifier can't be fooled. Both verifier conditions hold, so $L\in NP$. Since $L$ was arbitrary, $P\subseteq NP$. $■$ Where the case-split matters: NP's definition has two obligations (completeness for yes, soundness for no); we had to check both, and the "ignore $c$" trick satisfies each.

First, the precise definitions (the reductions here are always polynomial-time many-one reductions: a poly-time map $f$ with "$x$ is yes for $A$" $⟺$ "$f(x)$ is yes for $B$", written $A{\le }_{p}B$).

• $B$ is NP-hard if for every $L\in NP$ we have $L{\le }_{p}B$.
• $B$ is NP-complete if $B$ is NP-hard AND $B\in NP$.

Is the Halting Problem NP-complete? No.

• NP-hard: ✔ (every NP problem reduces to it — an all-powerful undecidable oracle can settle any poly-time-mapped instance).
• In NP: ✘ — a problem in NP has a poly-time verifier, but the Halting Problem has no decider at all (see Halting Problem (undecidability)), let alone a poly-time verifier. Since one of the two conjuncts fails, it is not NP-complete. It sits outside NP while still being NP-hard.

Invoke the Cook–Levin Theorem: SAT is NP-complete, i.e. every $L\in NP$ reduces to SAT in poly time. Let $L\in NP$ be arbitrary. By NP-completeness there is a poly-time reduction $f$ turning any instance $x$ (size $n$) into a SAT formula $f(x)$ of size $\le p(n)$ for some polynomial $p$, with "$x$ is yes" $⟺$ "$f(x)$ is satisfiable." Chain the algorithms:

1. Compute $f(x)$ — poly time $p(n)$.
2. Run the new SAT solver on $f(x)$ — time $O((p(n){)}^3)$, still polynomial (a polynomial of a polynomial is a polynomial).
3. Output its answer. This solves $L$ in poly time, so $L\in P$. Since $L$ was any NP problem, $NP\subseteq P$. Combined with $P\subseteq NP$ (Exercise 3.1) we get $P=NP$. $■$ Moral: one poly-time crack in a single NP-complete problem collapses the whole class — the "load-bearing pillar" idea from the parent note.

(b) — reduce the known-hard problem into $X$. Read a poly-time reduction $A{\le }_{p}B$ as "$A$ is no harder than $B$; $B$ is at least as hard as $A$." So:

• (b) Subset-Sum ${\le }_{p}X$ says $X$ is at least as hard as the NP-hard Subset-Sum ⇒ $X$ is NP-hard. ✔
• (a) $X{\le }_p$ Subset-Sum only says $X$ is no harder than something in NP ⇒ it shows $X\in NP$ (an upper bound), not hardness. ✘ Mnemonic: to prove hardness, map the monster onto your new problem, not the reverse.

Two independent errors:

1. "Slow known algorithm ⟹ not in P." The best algorithm, not the first one, decides membership in $P$. In 2002 the AKS algorithm decided primality in polynomial time, so PRIMES $\in P$. The old exponential methods said nothing about the true difficulty.
2. "Hard-looking ⟹ NP-complete." Even if a problem were hard, "hard" is not the same as "NP-complete" — NP-complete needs a proof of NP-hardness (every NP problem reduces to it) and membership in NP. No such proof exists for PRIMES; in fact it's in P. Verdict: both the premise and the leap are wrong; PRIMES is a poly-time (hence NP, hence not NP-complete unless $P=NP$) problem.

Link: RSA's security assumes FACTORING is easy to check (multiply the factors back — $O(n^2)$) but hard to find. FACTORING (as a decision problem, "does $N$ have a factor $\le k$?") is in NP: the certificate is a factor, the verifier is one division. If $P=NP$, then this NP problem is in $P$, so factoring gets a poly-time algorithm ⇒ RSA keys can be broken efficiently. So yes, in principle RSA falls. Honest caveats (the mastery point):

• $P=NP$ only guarantees some polynomial $n^k$ algorithm; the exponent/constant could be huge (e.g. $n^{100}$), so "poly" ≠ "instantly practical."
• The proof might be non-constructive — proving $P=NP$ without exhibiting the actual algorithm.
• RSA is broken by factoring specifically; a $P=NP$ proof breaks it if it yields (or implies) a usable factoring routine. So the correct statement is: $P=NP$ would destroy the theoretical foundation of RSA-style security, with practical impact depending on the algorithm's real-world efficiency.