The Class NP

A nondeterministic Turing machine (NTM) generalizes the ordinary (deterministic) Turing machine by allowing its transition function to specify a set of possible next configurations at each step, rather than a single one. Computation is no longer a single thread but a branching tree of possibilities. An NTM accepts an input if at least one branch of this tree reaches an accepting state; it need not be told which branch to take. The class NP (Nondeterministic Polynomial time) consists of all languages decided by some NTM whose longest accepting branch, on any input of length $n$, has length bounded by $p(n)$ for some fixed polynomial $p$. Intuitively, an NTM decides a language by being allowed to "guess" a solution and then verify it, where the guess itself costs no time — every guessed branch runs in parallel, free of charge. The second, more operational, definition replaces guessing with an explicit certificate (also called a witness or proof). A language $L$ is in NP if there exists a deterministic polynomial-time algorithm $V(x, c)$ — the verifier — and a polynomial $p$, such that for every string $x$:

Here $c$ is the certificate: for Sudoku it is the completed grid; for graph 3-colorability it is the coloring; for SAT it is a satisfying assignment. The verifier never has to search for $c$ — it is handed $c$ as extra input and only needs to check the claim, in time polynomial in $|x|$ alone. This definition matches ordinary programming intuition far better than nondeterministic branching does, which is why most NP-membership proofs in practice are given as "here is the certificate, here is the polynomial-time checker." Crucially, both definitions demand polynomial-size certificates and polynomial-time checking — dropping either bound trivializes the class (every language would qualify) or makes it far too weak. The word "nondeterministic" in NP is a historical artifact of the first definition; it does not mean "random" or "probabilistic." Nondeterminism here is a mathematical fiction — a bookkeeping device for "try everything at once" — used to define a class of languages, not a physically realizable machine.

View 1 — Nondeterministic Turing machine. An NTM is described by a transition function

mapping a (state, tape-symbol) pair to a set of possible (state, symbol, direction) triples, instead of a single triple as in the deterministic case. A computation is a tree: the root is the start configuration, and each node has one child per element of $\delta$ applicable there. The NTM accepts $x$ if some root-to-leaf path in this tree ends in the accept state. The running time of the NTM on $x$ is the length of the longest branch of the tree over all sequences of choices (finite, since we only consider machines that halt on every branch). NP is the set of languages decided this way in time $O(n^k)$ for some constant $k$.

View 2 — Verifier. A verifier $V$ is an ordinary deterministic algorithm taking two inputs, the instance $x$ and a candidate certificate $c$, and outputs accept or reject. $V$ runs in time polynomial in $|x|$ only (the certificate length is itself bounded by that same polynomial, so this is really a bound in terms of $|x|$ alone). $L$ is the language of $x$ for which some certificate makes $V$ accept. The two views are unified by a simple simulation argument in both directions. ``` // Simulating a verifier by a nondeterministic machine function NTM_SimulateVerifier(x): // "Guess" a string c of length at most p(|x|) nondeterministically choose c with |c| <= p(|x|) run V(x, c) // deterministic, polynomial time if V accepts: accept else: reject ``` ``` // Simulating a nondeterministic machine by a verifier function Verifier_SimulateNTM(x, c): // c encodes one path through N's computation tree: // a sequence of choice-indices, one per step, up to p(|x|) steps configuration := start configuration of N on x for i := 1 to p(|x|): options := delta(configuration.state, configuration.symbol) if c[i] is not a valid index into options: reject // malformed certificate configuration := apply(options[c[i]]) if configuration is accepting: accept reject // ran out of steps without accepting ``` The first snippet shows that "certificate + polynomial-time checker" can always be re-expressed as "nondeterministic guess + polynomial-time check on that branch": nondeterministic choice of a string is literally the same operation as guessing a certificate. The second snippet shows the converse: any single accepting branch of an NTM's computation tree is describable by a short string of choice indices — at most $p(n)$ of them, each needing $O(\log b)$ bits where $b$ is the (constant, machine-dependent) branching factor — so that string is a polynomial-size certificate, and replaying it deterministically is the verifier.

Complexity bookkeeping. Both formulations fix the same resource budget, just measured differently.

• Nondeterministic view: the NTM's longest branch, over all inputs of length $n$, is $O(n^k)$.
• Verifier view: certificate length $|c| \le p(n)$ and verifier running time $O(n^k)$ (as a function of $|x|=n$; note the verifier reads all of $c$ too, but $|c|$ is itself polynomial, so total time is still a polynomial in $n$).

Theorem (equivalence of the two definitions). A language $L$ is decided by a polynomial-time NTM if and only if $L$ has a polynomial-time verifier with polynomial-size certificates. Proof sketch, forward direction (NTM ⟹ verifier). Let $N$ be an NTM deciding $L$ in time $p(n)$, with branching factor bounded by a constant $b$ (the maximum number of choices $\delta$ ever offers). Fix $x \in L$. Some accepting branch of $N$'s computation tree on $x$ has length at most $p(|x|)$. Encode that branch as a string $c \in \{1,\dots,b\}^{p(|x|)}$, listing which choice was taken at each step (pad with a fixed symbol if the branch halted early). Then $|c| = O(p(|x|)\log b)$, still polynomial in $|x|$. Define the verifier $V(x,c)$ to replay $N$'s computation on $x$, at step $i$ following choice $c_i$, and to accept exactly when this replay reaches an accept state within $p(|x|)$ steps. $V$ is deterministic (no branching — $c$ resolves every choice) and runs in time polynomial in $|x|$, since each of the $p(|x|)$ replayed steps takes constant machine-work to simulate. By construction $V(x,c)$ accepts iff $c$ encodes an accepting branch, and such a $c$ exists iff $x \in L$ (since $N$ decides $L$). $\blacksquare$ Proof sketch, reverse direction (verifier ⟹ NTM). Let $V$ be a verifier for $L$ running in time $q(n)$ with certificates of length at most $p(n)$. Build an NTM $N$ that, on input $x$ of length $n$: (1) nondeterministically writes a string $c$ of length at most $p(n)$ onto a work tape, one symbol chosen per step from the tape alphabet (this is exactly what nondeterministic branching allows — trying every possible symbol at every position, in parallel branches); (2) deterministically simulates $V(x,c)$ and accepts iff $V$ accepts. Every branch of $N$ corresponds to one candidate certificate $c$; some branch accepts iff some certificate makes $V$ accept, i.e., iff $x \in L$. The longest branch takes $O(p(n))$ steps to write $c$ plus $O(q(n))$ steps to simulate $V$, which is polynomial in $n$. So $N$ decides $L$ in nondeterministic polynomial time. $\blacksquare$ Together these two directions establish the equivalence, which is why textbooks freely use "guess and check" language for both formulations interchangeably — they are formally the same class.

Why P ⊆ NP. Any language decidable in deterministic polynomial time is trivially in NP: use the empty certificate ($c = \varepsilon$) and let the verifier simply run the deterministic polynomial-time decider on $x$, ignoring $c$. So every polynomial-time-decidable language is polynomial-time verifiable. This containment is unconditional and easy; the reverse containment $NP \subseteq P$ is precisely the open P vs NP question.

Honest tradeoffs. NP membership proofs are usually much easier to produce than P membership proofs, because you only need to exhibit a certificate format and a fast checker — you never need to explain how to find the certificate. This is both NP's power (it captures an enormous swath of natural search problems) and its limitation as a class: NP says nothing constructive about how to solve the problem, only how to confirm a proposed answer. Also note that NP is a class of decision problems (yes/no answers), not optimization or search problems directly, though decision versions ("is there a tour of length $\le k$?") usually capture the difficulty of the corresponding search version via binary search over $k$ and repeated querying.

Take Subset Sum: given a finite set of integers $S = \{s_1,\dots,s_n\}$ and a target $t$, decide whether some subset of $S$ sums exactly to $t$.

Concrete instance: $S = \{3, 7, 11, 2, 9\}$, $t = 20$.

The verifier's pseudocode is short and unambiguous: ``` function Verify_SubsetSum(S, t, c): // c is a bit-vector of length |S|; c[i] = 1 means s_i is selected if length(c) != length(S): reject total := 0 for i := 1 to length(S): if c[i] == 1: total := total + S[i] if total == t: accept else: reject ``` This runs in $O(n)$ arithmetic steps — certainly polynomial in the input size (the number of bits needed to write down $S$ and $t$) — and the certificate $c$ has length exactly $n$ bits, also polynomial. This confirms SUBSET-SUM $\in$ NP, regardless of the fact that no polynomial-time algorithm is known to construct such a $c$ from scratch (the best known exact algorithms are exponential in the worst case, though pseudo-polynomial dynamic programming exists when $t$ is small in magnitude — itself a subtlety about what "efficient" means for numeric problems). Contrast this with the nondeterministic-machine view on the same instance: an NTM would, in parallel branches, try every possible bit-vector of length 5 (there are $2^5 = 32$ of them), and on the branch corresponding to $\{7,11,2\}$, it would compute the sum and accept. The bit-vector $10110$ is precisely the "choice sequence" from the equivalence proof above — nondeterministic guessing and certificate-supplying are the same act described in two languages.

The formal machinery of nondeterministic computation and polynomial-time reducibility crystallized in the early 1970s, though its roots trace to Turing's foundational model of computation decades earlier.

NP is not an abstract curiosity confined to textbooks — its reach extends across nearly every corner of applied computing. Cryptography leans on the presumed hardness of NP problems (and harder ones): the security of RSA and related schemes rests on factoring and discrete-log problems that are easy to verify but believed hard to invert, a direct descendant of the NP intuition (though factoring's exact classification relative to P and NP-completeness is itself subtle). Package managers and dependency resolvers (like those in Linux distributions) solve NP-hard constraint-satisfaction instances daily, using heuristics and SAT-solvers rather than guaranteed-fast exact algorithms. Chip design and formal verification tools translate circuit-equivalence and timing-closure problems into SAT instances — leveraging decades of engineering progress on NP-complete SAT solving even though worst-case exponential blowup is never fully eliminated. Operations research — airline scheduling, vehicle routing, exam timetabling — routinely formulates NP-hard optimization problems and accepts approximate or heuristic solutions in production because exact polynomial algorithms are not known to exist. Machine learning training itself touches NP territory: certain neural-network training and clustering formulations (e.g., exact k-means, certain combinatorial feature-selection problems) are NP-hard, motivating the widespread use of convex relaxations and gradient-based approximations instead of exact solvers. Understanding NP precisely tells engineers when to stop searching for a fast exact algorithm and instead invest in heuristics, approximation guarantees, or domain-specific structure — a judgment call underlying an enormous fraction of real-world software engineering for hard problems.

Ask the tutor: Can you show me why Hamiltonian Path is in NP, step by step, using the certificate definition?