Exercises — NP — non-deterministic polynomial, verifier definition

NP = Nondeterministic Polynomial time. It is about checking: a problem is in NP when a proposed solution can be verified quickly, even if finding one from scratch might be slow. It is not "non-polynomial."

• $x$ ::: the input instance
• $c$ ::: the certificate / witness
• $V$ ::: the deterministic poly-time checker (verifier)
• $p$ ::: the polynomial length bound, giving $|c|\le p(|x|)$

• (a) True. A solver is a verifier — run it and ignore the certificate ($c=\epsilon$). So $\text{P}\subseteq \text{NP}$.
• (b) False. NP = Nondeterministic Polynomial. It contains the easy class P; it is about fast verification, not about being unsolvable.
• (c) False. Nondeterminism accepts if some branch accepts (a logical OR over guesses). Randomness weighs branches by probability. Different models.

• Certificate $c$: the list of $k$ vertex labels claimed to form the clique.
• Length: at most $k$ labels, each $\le {\log }_{2}n$ bits, so $|c|\le k{\log }_{2}n\le n{\log }_{2}n$ — polynomial in the input size. ✔ (Short)
• Verifier $V$: check that all $k$ vertices are distinct, and that for every pair $(u,v)$ among them the edge $uv$ is present. There are $\left(\genfrac{}{}{0ex}{}{k}{2}\right)\le \left(\genfrac{}{}{0ex}{}{n}{2}\right)=O(n^2)$ pairs, each looked up in constant time — polynomial. ✔ (Fast)
• Yes-only: if a $k$-clique exists, listing its vertices makes $V$ accept; if none exists, no list of $k$ pairwise-adjacent vertices can be produced, so no certificate works. ✔

• Certificate: the subset itself — encode it as a bit-string $c\in \{0,1{\}}^n$ where bit $i$ is $1$ iff $a_i$ is chosen.
• Length: exactly $n$ bits. Polynomial. ✔
• Verifier: add up the chosen numbers and compare to $T$. Adding $n$ numbers is polynomial in the input size (the numbers are part of the input, so their bit-lengths are already counted). ✔
• Yes-only: a valid subset makes the sum equal $T$ and $V$ accepts; if no subset hits $T$, every $c$ fails. ✔

• Certificate: an assignment of one color from $\{1,2,3\}$ to each of the $n$ vertices.
• Length: $n$ symbols, each needing $2$ bits, so $2n$ bits. Polynomial. ✔
• Verifier: scan every edge $uv$ and check $\text{color}(u)\ne \text{color}(v)$. With $m$ edges this is $O(m)=O(n^2)$. ✔
• Yes-only: a proper coloring passes all edge checks; if the graph is not 3-colorable, some edge fails under every coloring. ✔

Take any decidable language $L$ decided by some algorithm $M$ (possibly very slow). Let the certificate $c$ be the entire accepting computation trace of $M$ on $x$ — the full sequence of machine configurations. A verifier can check "each step follows the transition rules and the last step accepts" in time linear in the trace length.

With no length bound the trace is allowed to be astronomically long (exponential, or worse), and $V$'s "poly time" is measured against the certificate too — so $V$ trivially runs in time polynomial in $|c|$ while $|c|$ itself is unbounded. Every decidable language sneaks in.

The clause that collapsed: Short. Bounding $|c|\le p(|x|)$ is precisely what stops "check a whole giant computation" from qualifying. Without it, NP would equal the class of all decidable languages.

If certificates stay polynomially short but $V$ may run in exponential time, then $V$ can — with an empty certificate — simply solve the problem by brute force. Any problem in EXP (exponential time, defined at the top of this page) now "qualifies," because the exponential verifier just re-solves it and ignores $c$.

That defeats the entire point: NP was meant to isolate "checking is easy," and an exponential checker is not easy checking — it is solving in disguise. The clause that collapsed: Fast. Polynomial-time verification is what makes "verify" genuinely cheaper than "solve" (unless P = NP).

Requiring a short, poly-checkable certificate for no instances is the definition of co-NP: $L\in \text{co-NP}$ iff its complement $\bar{L}\in \text{NP}$. Demanding certificates for both answers means the language is in $\text{NP}\cap \text{co-NP}$.

Whether $\text{NP}=\text{co-NP}$ is open and widely believed false. Example asymmetry: for SAT a "yes" is proved by exhibiting a satisfying assignment, but no one knows a short certificate that a formula is unsatisfiable (that would put SAT in co-NP, hence NP = co-NP). This one-sidedness is the whole reason NP and co-NP look different.

PARITY is in P — count the 1s in a single linear scan. To place it in NP explicitly:

• Certificate: the empty string, $c=\epsilon$. Length $0\le p(|x|)$ trivially. ✔
• Verifier $V(x,\epsilon )$: ignore $c$, scan $x$, count 1s, accept iff the count is even. This is $O(|x|)$ — polynomial. ✔
• Yes-only: $V$ accepts exactly when $x$ genuinely has even parity; the (empty) certificate exists for every yes instance and its acceptance depends only on $x$. ✔

This is the general pattern: any solver becomes a "lazy verifier" that discards the hint. Hence $\text{P}\subseteq \text{NP}$.

Enumerate all binary strings of length $\le p(|x|)=|x{|}^2$. The number of such strings is ${\sum }_{k=0}^{|x{|}^2}{2}^k=2^{|x{|}^2+1}-1<2^{|x{|}^2+1}.$ Each is fed to $V$ at cost $|x{|}^3$. Total time $T(|x|)<|x{|}^3\cdot 2^{|x{|}^2+1}.$ This is dominated by the $2^{|x{|}^2+1}$ factor, which is $2^{\text{poly}(|x|)}$ — exactly the shape of EXP (defined at the top of the page). So the brute-force verifier decides $L$ in exponential time, giving $\text{NP}\subseteq \text{EXP}$. ✔ (Accept iff any enumerated certificate makes $V$ accept — a giant OR, echoing the nondeterministic machine.)

A poly-time reduction $\text{SAT}{\le }_p\text{CLIQUE}$ means: any NP problem, first reduced to SAT (Cook–Levin), then to CLIQUE, ends up as a CLIQUE instance. So the reduction alone establishes exactly one thing:

1. CLIQUE is NP-hard — at least as hard as everything in NP.

But NP-hardness says nothing about whether CLIQUE is itself in NP — an NP-hard problem can lie far outside NP (some are even undecidable). To upgrade to NP-complete you must additionally supply the missing half: 2. the membership assumption $\text{CLIQUE}\in \text{NP}$ — proved by exhibiting a certificate (the vertex set) and a poly-time verifier, exactly as in Exercise 2.1.

NP-complete = NP-hard AND in NP. The reduction gives the hardness; the certificate gives the membership. The single fact you must isolate and prove is $\text{CLIQUE}\in \text{NP}$. (Separately, whether these NP-complete problems fall into P is the genuinely open P vs NP question.)

A number $N>1$ is prime iff there exists a generator $g$ of the multiplicative group $\{1,\dots ,N-1\}$ under multiplication mod $N$ — i.e. $g$ has multiplicative order exactly $N-1$. That happens iff:

1. $g^{N-1}\equiv 1(\mathrm{mod}N)$, and
2. for every prime factor $q$ of $N-1$, $g^{(N-1)/q}\not\equiv 1(\mathrm{mod}N)$ (so no smaller exponent works, forcing the order to be the full $N-1$).

Certificate (Pratt certificate): the generator $g$, the complete list of prime factors $q_1,\dots ,q_r$ of $N-1$, and — recursively — a Pratt primality certificate for each factor $q_j$ (so a verifier can trust that each $q_j$ really is prime rather than taking it on faith). The recursion bottoms out at small primes like $2$, which are certified directly.

• Length: each recursive level shrinks the number by a factor of at least $2$ (the factors $q_j$ multiply to $N-1$), so the recursion has depth $O(\log N)$ and the total certificate is $O((\log N{)}^2)$ bits — polynomial in $|x|=\log N$. ✔ (Short)
• Verifier: perform the two modular exponentiations in conditions (1) and (2) — fast modular exponentiation runs in time polynomial in $\log N$ — verify that the listed $q_j$ actually multiply to $N-1$, and recurse into each sub-certificate. The total work sums to a polynomial in $\log N$. ✔ (Fast)
• Yes-only: if $N$ is prime a generator exists (a standard theorem: the group $(\mathbb{Z}/N\mathbb{Z}{)}^{\times }$ is cyclic for prime $N$), so the certificate exists; if $N$ is composite, no element has order $N-1$, so conditions (1)–(2) fail for every candidate $g$ and no valid certificate can be built. ✔

Worked micro-example ($N=7$): take $g=3$. Then $N-1=6$ has prime factors $\{2,3\}$. Check (1): $3^6=729\equiv 1(\mathrm{mod}7)$. Check (2): $3^{6/2}=3^3=27\equiv 6\not\equiv 1$, and $3^{6/3}=3^2=9\equiv 2\not\equiv 1$. Both sub-conditions pass, so $g=3$ has order exactly $6=N-1$, certifying that $7$ is prime.

Thus $\text{PRIMES}\in \text{NP}$ — and since COMPOSITE $\in$ NP too, PRIMES lies in $\text{NP}\cap \text{co-NP}$. (Historically this was the strong hint that PRIMES is "not too hard," later confirmed by PRIMES $\in$ P.)

$\text{P}=\text{NP}$ would mean: for every problem where a solution can be checked in polynomial time, a solution can also be found in polynomial time. The certificate would not become useless — rather, the search for it would become as cheap as the check. The "hard-to-solve / easy-to-check" asymmetry that defines the practical interest of NP would vanish: SAT, CLIQUE, HAM-CYCLE, 3-COLOR would all get efficient solvers.

Because that would break most modern cryptography (which relies on the gap), and because decades of effort found no such algorithm, the consensus expectation is $\text{P}\ne \text{NP}$ — but it remains the central open open problem.

A nondeterministic machine at each step may branch into several choices; it accepts $x$ if some path of choices leads to accept. Freeze one accepting path and write down, in order, every choice it made — that string of choices is a certificate $c$. Feeding $c$ back into a deterministic machine that "replays the choices instead of guessing them" is exactly the verifier $V(x,c)$.

Conversely, given a verifier $V$ and bound $p$, build a nondeterministic machine that first guesses a string of length $\le p(|x|)$ (branching on each bit), then runs $V$ deterministically; it accepts iff some guess is a valid certificate.

Running-time equivalence: a poly-time nondeterministic machine ⇔ a poly-time deterministic verifier with a polynomially bounded certificate. The guess length is bounded by the machine's running time (poly), matching $|c|\le p(|x|)$; the deterministic replay is poly. Same time budget on both sides ⇒ same class, NP.

For any language, could you (a) name a certificate, (b) bound its length by a polynomial, and (c) describe a poly-time check? If yes to all three, it is in NP — Short, Fast, Yes-only.