NP-completeness is a form of bad news: evidence that manyimportant problems can't be solved quickly.
Why should we care?
These NP-complete problems really come up all the time. Knowingthey're hard lets you stop beating your head against a wall tryingto solve them, and do something better:
- Use a heuristic. If you can't quickly solve the problem with agood worst case time, maybe you can come up with a method forsolving a reasonable fraction of the common cases.
- Solve the problem approximately instead of exactly. A lot ofthe time it is possible to come up with a provably fast algorithm,that doesn't solve the problem exactly but comes up with a solutionyou can prove is close to right.
- Use an exponential time solution anyway. If you really have tosolve the problem exactly, you can settle down to writing anexponential time algorithm and stop worrying about finding a bettersolution.
- Choose a better abstraction. The NP-complete abstract problemyou're trying to solve presumably comes from ignoring some of theseemingly unimportant details of a more complicated real worldproblem. Perhaps some of those details shouldn't have been ignored,and make the difference between what you can and can't solve.
Classification of problems
The subject of computational complexity theory is dedicatedto classifying problems by how hard they are. There are manydifferent classifications; some of the most common and useful arethe following. (One technical point: these are all really definedin terms of yes-or-no problems -- does a certain structure existrather than how do I find the structure.)- P. Problems that can be solved in polynomial time. ("P"stands for polynomial.) These problems have formed the mainmaterial of this course.
- NP. This stands for "nondeterministic polynomial time"where nondeterministic is just a fancy way of talking aboutguessing a solution. A problem is in NP if you can quickly (inpolynomial time) test whether a solution is correct (withoutworrying about how hard it might be to find the solution). Problemsin NP are still relatively easy: if only we could guess the rightsolution, we could then quickly test it.
NP does not stand for "non-polynomial". There are manycomplexity classes that are much harder than NP.
- PSPACE. Problems that can be solved using a reasonableamount of memory (again defined formally as a polynomial in theinput size) without regard to how much time the solutiontakes.
- EXPTIME. Problems that can be solved in exponentialtime. This class contains most problems you are likely to run into,including everything in the previous three classes. It may besurprising that this class is not all-inclusive: there are problemsfor which the best algorithms take even more than exponentialtime.
- Undecidable. For some problems, we can prove that thereis no algorithm that always solves them, no matter how much time orspace is allowed. One very uninformative proof of this is based onthe fact that there are as many problems as there real numbers, andonly as many programs as there are integers, so there are notenough programs to solve all the problems. But we can also defineexplicit and useful problems which can't be solved.
Examples of problems in different classes
Example 1: Long simple paths.A simple path in a graph is just one without any repeatededges or vertices. To describe the problem of finding long paths interms of complexity theory, we need to formalize it as a yes-or-noquestion: given a graph G, vertices s and t, and a number k, doesthere exist a simple path from s to t with at least k edges? Asolution to this problem would then consist of such a path.
Why is this in NP? If you're given a path, you can quickly lookat it and add up the length, double-checking that it really is apath with length at least k. This can all be done in linear time,so certainly it can be done in polynomial time.
However we don't know whether this problem is in P; I haven'ttold you a good way for finding such a path (with time polynomialin m,n, and K). And in fact this problem is NP-complete, so webelieve that no such algorithm exists.
There are algorithms that solve the problem; for instance, listall 2^m subsets of edges and check whether any of them solves theproblem. But as far as we know there is no algorithm that runs inpolynomial time.
Suppose we have an encryption function e.g.
code=RSA(key,text)The "RSA" encryption works by performing some simple integerarithmetic on the code and the key, which consists of a pair (p,q)of large prime numbers. One can perform the encryption only knowingthe product pq; but to decrypt the code you instead need to know adifferent product, (p-1)(q-1).
A standard assumption in cryptography is the "known plaintextattack": we have the code for some message, and we know (or canguess) the text of that message. We want to use that information todiscover the key, so we can decrypt other messages sent using thesame key.
Formalized as an NP problem, we simply want to find a key forwhich code=RSA(key,text). If you're given a key, you can test it bydoing the encryption yourself, so this is in NP.
The hard question is, how do you find the key? For the code tobe strong we hope it isn't possible to do much better than a bruteforce search.
Another common use of RSA involves "public key cryptography": auser of the system publishes the product pq, but doesn't publish p,q, or (p-1)(q-1). That way anyone can send a message to that userby using the RSA encryption, but only the user can decrypt it.Breaking this scheme can also be thought of as a different NPproblem: given a composite number pq, find a factorization intosmaller numbers.
One can test a factorization quickly (just multiply the factorsback together again), so the problem is in NP. Finding afactorization seems to be difficult, and we think it may not be inP. However there is some strong evidence that it is not NP-completeeither; it seems to be one of the (very rare) examples of problemsbetween P and NP-complete in difficulty.
We've seen in the news recently a match between the world chesschampion, Gary Kasparov, and a very fast chess computer, Deep Blue.The computer lost the match, but won one game and tied others.
What is involved in chess programming? Essentially the sequencesof possible moves form a tree: The first player has a choice of 20different moves (most of which are not very good), after each ofwhich the second player has a choice of many responses, and so on.Chess playing programs work by traversing this tree finding whatthe possible consequences would be of each different move.
The tree of moves is not very deep -- a typical chess game mightlast 40 moves, and it is rare for one to reach 200 moves. Sinceeach move involves a step by each player, there are at most 400positions involved in most games. If we traversed the tree of chesspositions only to that depth, we would only need enough memory tostore the 400 positions on a single path at a time. This muchmemory is easily available on the smallest computers you are likelyto use.
So perfect chess playing is a problem in PSPACE. (Actually onemust be more careful in definitions. There is only a finite numberof positions in chess, so in principle you could write down thesolution in constant time. But that constant would be very large.Generalized versions of chess on larger boards are in PSPACE.)
The reason this deep game-tree search method can't be used inpractice is that the tree of moves is very bushy, so that eventhough it is not deep it has an enormous number of vertices. Wewon't run out of space if we try to traverse it, but we will runout of time before we get even a small fraction of the way through.Some pruning methods, notably "alpha-beta search" can help reducethe portion of the tree that needs to be examined, but not enoughto solve this difficulty. For this reason, actual chess programsinstead only search a much smaller depth (such as up to 7 moves),at which point they don't have enough information to evaluate thetrue consequences of the moves and are forced to guess by usingheuristic "evaluation functions" that measure simple quantitiessuch as the total number of pieces left.
If I give you a three-dimensional polygon (e.g. as a sequence ofvertex coordinate triples), is there some way of twisting andbending the polygon around until it becomes flat? Or is itknotted?
There is an algorithm for solving this problem, which is verycomplicated and has not really been adequately analyzed. However itruns in at least exponential time.
One way of proving that certain polygons are not knots is tofind a collection of triangles forming a surface with the polygonas its boundary. However this is not always possible (withoutadding exponentially many new vertices) and even when possible it'sNP-complete to find these triangles.
There are also some heuristics based onfinding a non-Euclidean geometry for the space outside of aknot that work very well for many knots, but are not known towork for all knots. So this is one of the rare examples of aproblem that can often be solved efficiently in practice eventhough it is theoretically not known to be in P.
Certain related problems in higher dimensions (is thisfour-dimensional surface equivalent to a four-dimensional sphere)are provably undecidable.
Suppose you're working on a lab for a programming class, havewritten your program, and start to run it. After five minutes, itis still going. Does this mean it's in an infinite loop, or is itjust slow?
It would be convenient if your compiler could tell you that yourprogram has an infinite loop. However this is an undecidableproblem: there is no program that will always correctly detectinfinite loops.
Some people have used this idea as evidence that people areinherently smarter than computers, since it shows that there areproblems computers can't solve. However it's not clear to me thatpeople can solve them either. Here's an example:
main() { int x = 3; for (;;) { for (int a = 1; a <= x; a++) for (int b = 1; b <= x; b++) for (int c = 1; c <= x; c++) for (int i = 3; i <= x; i++) if(pow(a,i) + pow(b,i) == pow(c,i)) exit; x++; } }This program searches for solutions to Fermat's last theorem. Doesit halt? (You can assume I'm using a multiple-precision integerpackage instead of built in integers, so don't worry aboutarithmetic overflow complications.) To be able to answer this, youhave to understand the recent proof of Fermat's last theorem. Thereare many similar problems for which no proof is known, so we areclueless whether the corresponding programs halt. Problems of complexity theory
The most famous open problem in theoretical science is whether P =NP. In other words, if it's always easy to check a solution, shouldit also be easy to find the solution?We have no reason to believe it should be true, so theexpectation among most theoreticians is that it's false. But wealso don't have a proof...
So we have this nice construction of complexity classes P and NPbut we can't even say that there's one problem in NP and not in P.So what good is the theory if it can't tell us how hard anyparticular problem is to solve?
NP-completeness
The theory of NP-completeness is a solution to the practicalproblem of applying complexity theory to individual problems.NP-complete problems are defined in a precise sense as the hardestproblems in P. Even though we don't know whether there is anyproblem in NP that is not in P, we can point to an NP-completeproblem and say that if there are any hard problems in NP, thatproblems is one of the hard ones.(Conversely if everything in NP is easy, those problems areeasy. So NP-completeness can be thought of as a way of making thebig P=NP question equivalent to smaller questions about thehardness of individual problems.)
So if we believe that P and NP are unequal, and we prove thatsome problem is NP-complete, we should believe that it doesn't havea fast algorithm.
For unknown reasons, most problems we've looked at in NP turnout either to be in P or NP-complete. So the theory ofNP-completeness turns out to be a good way of showing that aproblem is likely to be hard, because it applies to a lot ofproblems. But there are problems that are in NP, not known to be inP, and not likely to be NP-complete; for instance the code-breakingexample I gave earlier.
Reduction
Formally, NP-completeness is defined in terms of "reduction" whichis just a complicated way of saying one problem is easier thananother.We say that A is easier than B, and write A < B, if we canwrite down an algorithm for solving A that uses a small number ofcalls to a subroutine for B (with everything outside the subroutinecalls being fast, polynomial time). There are several minorvariations of this definition depending on the detailed meaning of"small" -- it may be a polynomial number of calls, a fixed constantnumber, or just one call.
Then if A < B, and B is in P, so is A: we can write down apolynomial algorithm for A by expanding the subroutine calls to usethe fast algorithm for B.
So "easier" in this context means that if one problem can besolved in polynomial time, so can the other. It is possible for thealgorithms for A to be slower than those for B, even though A <B.
As an example, consider the Hamiltonian cycle problem. Does agiven graph have a cycle visiting each vertex exactly once? Here'sa solution, using longest path as a subroutine:
for each edge (u,v) of G if there is a simple path of length n-1 from u to v return yes // path + edge form a cycle return noThis algorithm makes m calls to a longest path subroutine, and doesO(m) work outside those subroutine calls, so it shows thatHamiltonian cycle < longest path. (It doesn't show thatHamiltonian cycle is in P, because we don't know how to solve thelongest path subproblems quickly.)
As a second example, consider a polynomial time problem such asthe minimum spanning tree. Then for every other problem B, B <minimum spanning tree, since there is a fast algorithm for minimumspanning trees using a subroutine for B. (We don't actually have tocall the subroutine, or we can call it and ignore its results.)
Cook's Theorem
We are now ready to formally define NP-completeness. We say that aproblem A in NP is NP-complete when, for every other problem B inNP, B < A.This seems like a very strong definition. After all, the notionof reduction we've defined above seems to imply that if B < A,then the two problems are very closely related; for instanceHamiltonian cycle and longest path are both about finding verysimilar structures in graphs. Why should there be a problem thatclosely related to all the different problems in NP?
Theorem: an NP-complete problem exists.
We prove this by example. One NP-complete problem can be foundby modifying the halting problem (which without modification isundecidable).
Bounded halting. This problem takes as input aprogram X and a number K. The problem is to find data which, whengiven as input to X, causes it to stop in at most Ksteps.
To be precise, this needs some more careful definition: whatlanguage is X written in? What constitutes a single step? Also fortechnical reasons K should be specified in unary notation,so that the length of that part of the input is K itself ratherthan O(log K).
For reasonable ways of filling in the details, this is in NP: totest if data is a correct solution, just simulate the program for Ksteps. This takes time polynomial in K and in the length ofprogram. (Here's one point at which we need to be careful: theprogram can not perform unreasonable operations such as arithmeticon very large integers, because then we wouldn't be able tosimulate it quickly enough.)
To finish the proof that this is NP-complete, we need to showthat it's harder than anything else in NP. Suppose we have aproblem A in NP. This means that we can write a program PA thattests solutions to A, and halts within polynomial time p(n) with ayes or no answer depending on whether the given solution is reallya solution to the given problem. We can then easily form a modifiedprogram PA' to enter an infinite loop whenever it would halt with ano answer. If we could solve bounded halting, we could solve A bypassing PA' and p(n) as arguments to a subroutine for boundedhalting. So A < bounded halting. But this argument works forevery problem in NP, so bounded halting is NP-complete.
How to prove NP-completeness in practice
The proof above of NP-completeness for bounded halting is great forthe theory of NP-completeness, but doesn't help us understand othermore abstract problems such as the Hamiltonian cycle problem.Most proofs of NP-completeness don't look like the one above; itwould be too difficult to prove anything else that way. Instead,they are based on the observation that if A < B and B < C,then A < C. (Recall that these relations are defined in terms ofthe existence of an algorithm that calls subroutines. Given analgorithm that solves A with a subroutine for B, and an algorithmthat solves B with a subroutine for C, we can just use the secondalgorithm to expand the subroutine calls of the first algorithm,and get an algorithm that solves A with a subroutine for C.)
As a consequence of this observation, if A is NP-complete, B isin NP, and A < B, B is NP-complete. In practice that's how weprove NP-completeness: We start with one specific problem that weprove NP-complete, and we then prove that it's easier than lots ofothers which must therefore also be NP-complete.
So e.g. since Hamiltonian cycle is known to be NP-complete, andHamiltonian cycle < longest path, we can deduce that longestpath is also NP-complete.
Starting from the bounded halting problem we can show that it'sreducible to a problem of simulating circuits (we know thatcomputers can be built out of circuits, so any problem involvingsimulating computers can be translated to one about simulatingcircuits). So various circuit simulation problems are NP-complete,in particular Satisfiability, which asks whether there is an inputto a Boolean circuit that causes its output to be one.
Circuits look a lot like graphs, so from there it's another easystep to proving that many graph problems are NP-complete. Most ofthese proofs rely on constructing gadgets, small subgraphsthat act (in the context of the graph problem under consideration)like Boolean gates and other components of circuits.
There are many problems already known to be NP-complete, andlisted in the bible of the subject:
Computers and Intractibility:If you suspect a problem you're looking at is NP-complete, thefirst step is to look for it in Garey and Johnson. The second stepis to find as similar a problem as you can in Garey and Johnson,and prove a reduction showing that similar problem to be easierthan the one you want to solve. If neither of these works, youcould always go back to the methods described in the rest of thisclass, and try to find an efficient algorithm...
A guide to the theory of NP-completeness
Michael R. Garey and David S. Johnson
W. H. Freeman, 1979.
ICS 161 -- Dept.Information & Computer Science -- UC Irvine
Last update:
