NP-Completeness from Scratch — Not Unsolvable, but Fast to Verify

NP does not stand for Non-Polynomial. It is the class of problems where, if someone hands you an answer, you can check it quickly. We build up P vs NP, reductions and NP-completeness from zero, then look at how all of it shows up in shift rosters and delivery routes.

Think about a Sudoku puzzle

Solving a Sudoku is work. You narrow down candidates, hit a wall, back up, try again. But hand someone a finished grid and ask "is this right?" and the check takes seconds — just confirm that every row, column and box contains 1 through 9 exactly once.

Hard to solve, easy to check. That asymmetry is exactly what the most famous open problem in complexity theory, P vs NP, is about.

Let me kill one misconception first. NP does not stand for Non-Polynomial. It stands for Nondeterministic Polynomial, and the meaning leans the opposite way. Saying "this problem is in NP" does not say it is hard — it says the answer is fast to verify. If you carry the wrong reading into a design review and announce "it's NP, so we can't do it," you are saying something technically false.

P — problems we can solve in polynomial time

Let $n$ be the size of the input: a graph with $n$ vertices, a list with $n$ elements, that kind of scale. P is the set of problems whose running time is bounded by a polynomial in $n$ — $n$, $n\log n$, $n^2$, $n^3$, and so on. Sorting, shortest paths and primality testing all live here.

Why draw the line at "polynomial", which seems awfully coarse? Because it survives composition. If a polynomial-time procedure calls another polynomial-time procedure a polynomial number of times, the whole thing is still polynomial. The classification doesn't break when you assemble parts. Differences in instruction set or memory model also get absorbed into the polynomial slack, so "is it in P?" is a property of the problem rather than of a particular CPU.

None of which means $n^{100}$ is usable in practice. What Big-O deliberately throws away is covered in Computational Complexity from Scratch.

NP — you can check it fast once you're shown the answer

NP is defined by verification, not by solving.

Consider problems with a yes/no answer. For inputs whose answer is "yes", suppose you can attach a certificate — evidence for the claim. For Sudoku, the filled grid. For "is there a tour visiting every city within 1000 km?", the actual ordering of cities. For "is there an assignment making this formula true?", the assignment itself.

If the certificate's length is polynomial in the input size and checking it takes polynomial time, the problem is in NP.

In plain words: $x$ is the input, $L$ is the set of inputs whose answer is yes, $w$ is the certificate, $p$ is some polynomial, and $V$ is a verifier that runs in polynomial time. Equation (1) reads "the answer for $x$ is yes exactly when there exists a polynomial-sized certificate $w$ that the verifier accepts." The crucial part is what is absent: nothing here says how much effort it takes to find $w$. Someone hands it to you; you only have to check.

$\mathrm{P} \subseteq \mathrm{NP}$ falls out immediately — if you can solve it quickly yourself, the certificate can be empty and the verifier just re-solves the problem. The open direction is the reverse: is $\mathrm{P} = \mathrm{NP}$? It is one of the Millennium Prize Problems selected by the Clay Mathematics Institute in 2000, carrying a $1 million prize. Most researchers expect $\mathrm{P} \ne \mathrm{NP}$, but there is no proof either way.

How unreasonable exponential growth really is

"Just brute force it" stops working at a scale that arrives sooner than intuition suggests.

Trying every subset of 50 elements means $2^{50} \approx 1.13\times10^{15}$ combinations. Even on a hypothetical machine checking a billion per second, that is about 13 days. At 100 elements it becomes $2^{100} \approx 1.27\times10^{30}$, which on the same machine takes over a thousand times the age of the universe.

Here is the genuinely nasty part: make the machine 1000× faster and the reachable $n$ grows by about 10 (because $2^{10}=1024$). Exponential time is close to the only regime where waiting for better hardware is structurally useless.

Reduction — dressing one problem up as another

Rather than arguing about each problem in isolation, we introduce a tool for translating problems into each other and comparing them.

If you can convert any input of problem A into an input of problem B in polynomial time, such that B's answer on the converted input is A's answer on the original, we say A reduces to B and write $A \le_p B$.

Take timetabling and dress it up as graph coloring. Make each class a vertex. Draw an edge between any two classes that share a teacher, a room or a student group — the pairs that cannot run at once. Let time slots be colors. Then "adjacent vertices must not share a color" is literally "conflicting classes must not share a slot". The translation costs time proportional to the number of classes and conflicts, so it is polynomial. If coloring is easy, timetabling is easy.

The inequality-shaped symbol is no accident: $A \le_p B$ means "A is at most as hard as B". And this is where people go wrong most often. If you want to show that your problem is hard, the translation must run from a known hard problem into your problem. Building the reverse direction only tells you your problem might be easier than the known one — it proves nothing about hardness.

NP-complete — the hardest core of NP

A problem is NP-complete when two conditions hold:

1. It is itself in NP (its answers are fast to verify)
2. Every problem in NP reduces to it in polynomial time

Condition 2 is a startling claim: infinitely many problems all translate into this single one. Does such a thing exist? In 1971 Stephen Cook, and independently in 1973 Leonid Levin, showed that SAT — the Boolean satisfiability problem — is exactly that.

Once one foundation exists, the rest cascades. Exhibit a single reduction from SAT to a new problem and, by transitivity, all of NP reduces to it too. In 1972 Richard Karp used this to establish 21 classic combinatorial problems as NP-complete in one stroke: clique, vertex cover, graph coloring, subset sum, Hamiltonian cycle — a list every practitioner eventually bumps into.

The consequence bites. If a polynomial-time algorithm is ever found for any one NP-complete problem, all of NP collapses into P that same instant. Conversely, the fact that nobody has cracked a single one in over half a century is the working engineer's reason for believing $\mathrm{P} \ne \mathrm{NP}$.

How NP-hard differs

NP-hard requires only condition 2 above; condition 1 is dropped. So NP-complete is a subset of NP-hard. The halting problem is NP-hard but sits outside NP entirely, since it is undecidable.

The other easily confused pair is decision versus optimization. NP-completeness is a term for yes/no decision problems. "Does a tour of total length at most $K$ exist?" is NP-complete; "find the shortest tour" is called NP-hard. What people ask you to build is almost always the latter, but the hardness argument is conventionally recast in terms of the former.

What you actually do once you know it's NP-complete

Learning that a problem is NP-complete is not a reason to give up — it is the signal to switch strategy. There are four moves.

1. Put it on an off-the-shelf solver. SAT solvers, MILP (mixed-integer programming) solvers and CP-SAT (constraint programming) solvers have exponential worst cases but exploit the structure real data contains. "NP-complete" is nowhere near "out of reach".

2. Give up on optimality. Two flavors: approximations with a proven guarantee (for the traveling salesman problem with distances obeying the triangle inequality, a classic method guarantees within 1.5× of optimal), and heuristics with no guarantee but real practical value. When to reach for the latter is covered in Simulated Annealing and Genetic Algorithms.

3. Bet on the structure of your inputs. If some parameter of real data stays small, the problem can drop to polynomial. Subset sum and knapsack fall to a DP over the target value $W$ in $O(nW)$ — but that scales with the value of $W$, which is why it's called pseudo-polynomial and why it collapses once $W$ gets large.

4. Redefine the problem. Dropping one constraint sometimes lands you back in P. SAT with three variables per clause is NP-complete; with two (2-SAT) it is polynomial. Asking "do we genuinely need that constraint?" is occasionally the cheapest optimization available.

The boundary, in code

Here is subset sum — can we pick numbers summing to exactly target? — done both ways.

from itertools import combinations

def subset_sum_bruteforce(nums, target):     # O(2^n)
    for r in range(len(nums) + 1):
        for c in combinations(nums, r):
            if sum(c) == target:
                return True
    return False

def subset_sum_dp(nums, target):             # O(n * target), pseudo-polynomial
    reachable = [False] * (target + 1)
    reachable[0] = True
    for x in nums:
        for s in range(target, x - 1, -1):   # each number used at most once
            reachable[s] |= reachable[s - x]
    return reachable[target]

The DP works because there are only $target+1$ subproblems worth remembering. Whether that table fits in the real world is precisely the line between polynomial and exponential.

The table-filling mindset is developed in Dynamic Programming from Scratch.

How this shows up on the job

Who, and when. A backend or optimization engineer asked to "generate the shift roster automatically" or "order the stops for 20 trucks". An infrastructure engineer packing VMs or containers onto hosts (bin packing). A compiler engineer implementing register allocation (graph coloring). Anyone writing dependency resolution for a package manager — many implementations run a SAT solver internally. The move is always the same: first ask whether this is one of the known NP-complete problems in disguise. If it is, you can decide to reach for a solver before writing your own brute-force search.

Knobs you actually touch. In OR-Tools CP-SAT: max_time_in_seconds to cut off search, num_search_workers for parallelism, AddHint to warm-start from an existing solution. On MILP solvers, relative_mip_gap (MIPGap in Gurobi) — how much distance from optimal you'll accept — is the workhorse in production. Models move around as LP or MPS files. For direct SAT/SMT work, Z3 and the MiniSat family.

Traps that turn into incidents.

• Shipping without a time limit. The worst case is exponential, so one slightly larger input spikes your latency. Always pair a cutoff with a defined feasible solution to return when the cutoff fires.
• Ignoring the solver's status code. Treating CP-SAT's OPTIMAL / FEASIBLE / INFEASIBLE as "we got an answer" leads to reporting a non-optimal solution as optimal, or missing that no solution exists at all.
• Conflating the worst case with your data. "It's NP-complete, so it's impossible" is technically wrong — real inputs are usually not worst cases. The reverse error is just as bad: "it was fast on our data" is fragile, because a small shift in the input distribution drops you onto the exponential branch.
• Not noticing that one added constraint changes the class. Bipartite matching is in P; three-way matching is NP-complete. Shortest path is in P; longest path is NP-hard. "It looks similar, so it's probably similar difficulty" simply does not hold. Re-examine the class every time the spec changes.
• Misreading an approximation ratio. "Within 1.5×" is a worst-case guarantee. It does not mean the average is 1.5×, and it is not a synonym for "close enough".

The question you get in a design review. "What makes you say this is NP-complete?" The right answer is never "it feels hard" — it is "because I can build a polynomial-time reduction from known NP-complete problem X into ours." And the follow-up is nearly always "is there a special case that lands in P?" Answering both moves the conversation from give up or not to how do we change the design.

Summary

• P means "fast to solve"; NP means "fast to check the answer". NP does not mean unsolvable
• A reduction dresses one problem as another. Unless it runs from a known hard problem into yours, it says nothing about hardness
• NP-complete is the hardest core of NP — crack one and they all fall
• In practice it isn't a verdict of "impossible", it's a signal: stop writing brute force, move to a solver, an approximation, or the structure of your data