P, NP and Hard Problems
Checking a finished sudoku takes a minute; filling one in can take an hour. That gap, easy to check and hard to find, defines the most famous open question in computer science. It also defines a list of problems working engineers meet every week: scheduling, routing, packing and choosing package versions that agree with each other.
Recognizing the shape is worth more than any single algorithm, because it tells you to stop looking for a fast exact one. Nobody has found one in more than fifty years of trying, and the growth numbers from Chapter 1 explain what happens to the team that tries anyway.
P: Solvable in Polynomial Time
P is the class of problems a program can solve in polynomial time: n, n squared, n cubed, the growth classes of Chapter 1 short of exponential. Sorting is in P. So are shortest paths from Chapter 8 and finding a prefix in a trie. The exponent can be large in theory, but the problems met in practice mostly sit at n log n, n squared or n cubed.
Polynomial is the line where better hardware still helps. A machine twice as fast handles 41% more input for an n squared algorithm, because the square root of 2 is about 1.41. For a 2 to the n algorithm the same machine handles exactly one more item. A thousand times faster buys about ten more items. Beyond the polynomial line, hardware stops being an answer.
NP: Easy to Check
A problem is in NP when a proposed answer can be checked in polynomial time. A filled sudoku is checked by reading each row, column and box once. A timetable is checked for clashes by looking at each pair of events that share a room. A delivery route is checked against a 300-kilometre limit by adding up its legs. Finding the answer is a different matter.
NP stands for "nondeterministic polynomial": a machine that could guess the right answer and then check it quickly. It does not stand for "not polynomial". Every problem in P is also in NP, because if you can find an answer quickly you can certainly check one quickly. For nine delivery stops, checking a route means adding nine legs, while finding the shortest means choosing among 20,160 distinct round trips.
NP-Complete: The Hardest of Them
Some problems in NP are universal: every problem in NP can be translated into them in polynomial time. In 1971 Stephen Cook showed that Boolean satisfiability is one. SAT asks whether some assignment of true and false to a formula's variables makes the whole formula true. Leonid Levin reached the same result independently, published in 1973. In 1972 Richard Karp showed 20 more, among them graph colouring, the knapsack problem and the Hamiltonian cycle, a round trip that visits every stop exactly once.
These are the NP-complete problems, and they stand or fall together. A fast algorithm for any one of them would give, through the translations, a fast algorithm for every problem in NP. So decades of failure to find one for any of them count as evidence about all of them.
The Shapes in Real Work
The shapes turn up everywhere once you know them. Scheduling: timetables, exam slots, staff rotas, the constraint search of Chapter 9. Routing: a delivery van's stops, the travelling salesman. Packing: containers onto machines, virtual machines onto hosts, files onto disks. A compiler assigning variables to a limited set of registers faces graph colouring, which Chapter 13 met. And installing packages whose versions constrain one another is NP-complete in general, which researchers showed in 2006 and every developer has felt as a resolver that thinks for a long time.
Exhaustive search means trying 2 to the n subsets or n factorial orderings, the classes Chapter 1 showed failing on inputs that look small. Twenty delivery stops have about 60 quadrillion distinct round trips. Sixty stops have about 7 times 10 to the 79, on the order of the estimated number of atoms in the observable universe. No hardware closes that gap.
P vs NP
Nobody knows whether every problem that is easy to check is also easy to solve. If P equals NP, every NP-complete problem has a fast algorithm that nobody has found. If P does not equal NP, none of them does. It is one of the seven Millennium Prize Problems the Clay Mathematics Institute named in 2000, with a million dollars for a proof either way, and it is still open.
Most researchers expect that P does not equal NP. Everything built on hardness, including the cryptography in the next topic, assumes something at least as strong, and assumes it without proof.
What Recognizing the Shape Buys
NP-completeness is a statement about the hardest inputs as the size grows without limit, and that leaves a great deal of room. Small instances fall to exact search: twenty jobs are a different problem from twenty thousand. Special structure can put a problem back in P: colouring a graph with two colours is easy while three is NP-complete, and satisfiability with two variables per clause is easy while three is NP-complete. The knapsack problem with small whole-number weights falls to the dynamic programming of Chapter 9.
The cost of missing the shape is a sprint spent hunting a fast exact scheduler for 200 jobs, fighting the growth curve instead of the code. The cost of seeing it is a design meeting that asks a different question: how good does the answer need to be, and how long can we wait for it? The next topic is what engineers do with that question.
Undecidable problems have no algorithm at all, as the previous topic proved for halting. Change the question, or accept a tool that is sometimes wrong.
NP-complete problems have correct algorithms, and every known one takes exponential time on the hardest inputs. Approximate, use a solver or shrink the problem.
Merely slow means an n squared method where an n log n one is known. Find the better algorithm. Diagnosing which of the three you face decides whether to keep searching.
- "NP means not polynomial." It means nondeterministic polynomial: the problems whose answers can be checked quickly. Every problem in P is in NP, and whether the two classes are the same is the open question.
- "NP-complete means unsolvable in practice." Industrial SAT solvers routinely handle instances with hundreds of thousands of variables and millions of clauses. The hardness is about the worst case, and real inputs often have structure a solver exploits.
- "A faster computer makes an exponential problem tractable." Doubling the speed lets a 2 to the n search handle one more item. A thousand times faster buys about ten.
- "Hard problems are academic puzzles." Timetables, delivery routes, bin packing on a cluster and dependency resolution are NP-hard in general, and most engineers meet one of them within a year.
- "It has been proven that P does not equal NP." It has not. It is what most researchers expect, and one of the best-known unsolved problems in mathematics.
- Recognize the scheduling, routing and packing shapes before designing. Naming the shape ends the search for a fast exact algorithm that nobody has found.
- Solve small instances exactly, and write down the size where exact search stops being affordable. The growth curve makes that size a hard limit, not a tuning question.
- Look for structure that puts your instance in P: small whole-number weights, a tree instead of a general graph, two choices instead of three. Special cases are often easy even when the general problem is not.
- Hand hard instances to a solver or an approximation instead of hand-written exhaustive search. Decades of engineering beat a sprint of it.
Knowledge Check
Which task is easy to check but, as far as anyone knows, hard to solve exactly at scale?
- Sorting a list of 2 million catalogue records by title
- Assigning 200 exams to slots so that no student has a clash
- Finding the shortest path between two stops on a road map
- Deciding whether an arbitrary build script eventually halts
A new server is twice as fast as the old one. How much larger an input can it handle in the same time for an n squared algorithm and a 2 to the n algorithm?
- Twice as large for both, since the machine is twice as fast
- About 41% larger for n squared; one more item for 2 to the n
- About 41% larger for 2 to the n; twice as large for n squared
- Four times as large for n squared; twice as large for 2 to the n
What does knowing that a scheduling problem is NP-complete tell you about next week's real inputs?
- Every input of any size will take exponential time to solve
- A solver will fail, so only random guessing is left to try
- Nothing definite: it describes the worst inputs as size grows
- They can be solved quickly if the hardware is recent enough
A developer claims a polynomial-time algorithm for the travelling salesman decision problem. If true, what would follow?
- Only routing problems would become fast; other puzzles stay hard
- Nothing much, since the travelling salesman is not in NP
- Halting could then be decided for programs up to a size
- Every problem in NP would be solvable in polynomial time
Which of these tasks is merely slow, rather than NP-complete or undecidable?
- Comparing every pair of 1 million records to find duplicates
- Packing 5,000 virtual machines onto hosts with the fewest hosts
- Proving that no input can make a given parser loop forever
- Picking package versions that satisfy every stated constraint
You got correct