Chapter 34 - Introduction
NP-Completeness

Overview

Good news: we've seen that such-and-such a problem can be solved quickly (in close to linear time, or at least a time that is some small polynomial function of the input size).

Bad news: NP-completeness: evidence that many important problems can't be solved quickly.

The key purpose of this chapter is categorizing algorithms as to their efficiency classes.

Some problems can not be solved algorithmically.

Example: Given a polynomial such as

x³yz+2y⁴z²-7xy⁵z=6

are there integers x, y, z that satisfy it?

Answer is that no algorithm can solve this problem.

Why? There may be a solution or not, but with an infinite number of possible integers to try, how does an algorithm determine when to stop? If it stops after checking n integers it maybe that the solution was n+1. Therefore algorithm cannot guarantee to solve the problem or to halt if there is no solution.

Example: Halting problem by Alan Turing.

Suppose we have a program p and input x.

To determine if p( x ) ever terminates, we write algorithm terminates(p, x), which tells us whether p ever stops on input x.

To test terminates we write:

f( Y ) while terminates( Y, Y ) do

and call by: f( f )

meaning the while stops only if program f does not terminate given its own code as input.

This creates a contradiction, either:

1. terminates( f, f ) is true, meaning f terminates, causing the while iteration to loop forever so f does not terminate!
2. terminates( f, f ) is false, meaning f does not terminate in which case it does terminate!

We saying that f terminates only if f does not terminate! Obviously a contradiction.

A more formal treatment:

Theorem: For program P and input X, no program H(P, X) that itself halts can return true if P(X) halts and false if P(X) fails to halt (infinite-loop). In simpler terms, in general, no algorithm can determine if another algorithm halts. Proof: Assume H exists: H(P, X) returns true if P(X) halts or false if P(X) fails to halt. Construct: F(Y) = if H(Y,Y) then while true; else true; Call F(F). H(F,F) is true when F(F) halts but F(F) can not halt when H(F,F) is true, because F(F) executes: while true. H(F,F) is false when F(F) does not halt, so F(F) returns true but F(F) does not halt, so never returns true. By contradiction, H cannot exist.

 

OK. The Halting Problem is unsolvable. Whatever. Why should you care?

Question: How can you prove the difference between a program in an infinite loop or just taking a long time?

There are other important unsolvable problems, such buffer overrun exploited by hackers.

 

Some problems can be solved algorithmically but not in a reasonable amount of time - most useful algorithms are solved in polynomial time.

The following presents several approaches to establishing the class of an algorithm.

 

Lower bounds arguments - If your solution best-base is worse than a known solution then ...

Compare the efficiency of algorithms solving the same problem.

Example: Selection sort is Ω(n²) as compared to merge-sort which is Ω(n lg n), the best we can hope to achieve.

Knowing the lower bound for any algorithm solving a particular problem tells us how much improvement we can hope to achieve.

If the bound is tight, we already know an algorithm in the same efficiency class as the lower bound, we can only improve by some constant factor.

Recall quicksort is Θ(n lg n) with very small constants.

Finding a lower bound class is simpler than finding the minimum number of operations required to solve a problem.

Example: Showing that finding the median of n numbers is Ω(n) (why?) is simple but showing that at least 3(n-1)/2 comparisons are required is in the worst case (odd n) is much more difficult.

Trivial lower bounds

Trivial lower bounds is based on counting the number of inputs and outputs; since a algorithm must read all inputs and write all outputs.

Example: Any algorithm generating all permutations of n items is Ω(n!) since must output n! permutations. This is a tight bound since good algorithms spend constant time on each permutation.

Example: Multiplication of two n-by-n matrices is Ω(n²) since any algorithm must process 2n² elements in the input of matrices.

Question:

• What is the class of the following algorithm?
• Is the trivial lower bound of Ω(n²) useful in this case?

MatrixMultiplication( A[n,n], B[n,n], C[n,n]) for i ←1 to n do for j ← 1 to n do C[i,j] ←0 for k ← 1 to n do C[i,j] ← C[i,j]+A[i,k]*B[k,j]

Trivial lower bounds are often too low to be useful.

Example: Traveling salesman problem has n(n-1)/2 inputs so is Ω(n²). But there is no known polynomial time algorithm.

Another obstacle to trivial lower bounds as a meaningful bounds is determining which input must be processed by the algorithm.

Example: Binary search inputs n sorted elements, Ω(n), but does not process all elements, Ω(lg n).

 

Information-theoretic arguments

Seeks to establish a lower-bound based on the amount of information produced.

Example: Consider the game of guessing a number between 1 and n using questions with yes/no answers. The uncertainty is ⌈lg n∧ , the number of bits needed to specify a particular number among the n possibilities. Each yes/no answer yields one bit of information.

Question:

• What questions would the questioner ask to ensure that the answer was always found after ⌈lg n∧ questions?
• How many questions are needed to determine the number for n=8?
• Give the decision tree for n=8.

You might recall that we used decision trees to establish the lower bound for all comparison sorts (see Chapter 8).

Example: The following decision tree finds the maximum of three numbers.

Converting algorithms to decision problems gives a yes/no answer.

Example: Convert "find the shortest-path from u to v" to "is there a path from u to v of at most k edges".

 

Deterministic algorithm

All algorithms examined so far have been deterministic. Deterministic algorithms always produce the same results for a given input.

Nondeterministic algorithm

Nondeterministic algorithms have two phases:

1. Nondeterministic guessing (think of as some random process) phase, each time the algorithm is run the resulting guess may differ.
2. Deterministic verification phase, checks that the guess is a solution, returning true or false, or looping infinitely.

Example: Nondeterministic graph coloring

Use 4 colors to color 5 vertices with all adjacent vertices a different color.

Guesses (vertex order 1-5):

• RRRRR        false    All vertices Red
• RYBRG        false    Adjacent vertices 1 and 4 Red
• RBYGO        false    Too many colors (5) used
• RGRBY        true     Valid 4-coloring

Question

• What is the complexity of verifying the answer?
• What is the complexity of sorting a list?
• What is the complexity of verifying a list is sorted?
• Do you think it is generally of lower complexity to verify an answer than find a solution?

 

NP-completeness and the class P and NP

class P - Polynomial or O(n^k) for k a constant

Consists of those problems that are solvable in polynomial time by a deterministic algorithm.

Its worst case efficiency is O(p(n)) where p(n) is a polynomial.

Note that for O notation, problems solvable in logarithmic or linear time are polynomial.

 

class NP - Nondeterministic Polynomial

Consists of those problems that are verifiable in polynomial time.

If given a solution, could verify the solution is correct in time polynomial based on the size of the input to the problem.

Example: We just demonstrated graph coloring can be verified correct in polynomial time.

Example: Hamiltonian Cycle Problem - Find a cycle in a graph visiting each vertex exactly once.

Example at right: 2 → 3 → 4 → 5 → 1

Given: an undirected graph G = (V, E)

A certificate would be a sequence of |V| vertices <v₁, v₂, ..., v_|V|>

To verify:

• check that each edge in the sequence (v_i, v_i+1) ∈ E(G), ∀ i: 1 ≤ i ≤ |V| - 1
• and the edge (v_|V|, v₁) ∈ E(G).

Verification can be done in polynomial time, Ω(|V|)

P | NP

 

class NPC - NP Complete

Consists of problems in NP and are as hard as any problem in NP

If any problem in NPC can be solved in polynomial time, then all problems in NPC can be solved in polynomial time.

We'll see why later in Section 34.4.

 

Most theoretical computer scientists believe that classes P and NPC are distinct, that NPC problems can be verified but not be solved in polynomial time.

So far, no NPC problem has been shown to have a polynomial time solution.

 

Showing Problems to be NP-complete

The course has been about analysis and design of algorithms, trying to prove existence of an efficient algorithm.

NP-complete, we try to show that no efficient algorithm exists.

Three key concepts for showing NP-complete:

1. Decision problems versus optimization problems

optimization problems

• Problems where each feasible (valid) solution has an associated value and we want to find the feasible solution with the best value.
  
• Example:
  • Shortest Path for undirected graph G, find the path from vertex u to vertex v that has the least number of edges
    
  • Assign n people to n jobs for the lowest cost (least time, etc.)

decision problems

• Problems where the solution is either "yes" or "no" (1 or 0)
  
• Example:
  • Shortest Path_D is a related decision problem for Shortest Path.
    
  • Shortest Path_D is a decision problem that takes undirected graph G = (V, E), vertices u and v, and an integer k and answers "yes" if there is a path from u to v of length k edges or less.
    
  • Job assignment as decision problem, takes nxn cost matrix and cost and answers "yes" if assignment is cost or less

NP-completeness applies directly only to decision problems, not optimization problems.

Can often easily cast optimization problem into decision problem, as in the examples above.

 

2. Reductions

Solve Problem A Using a Reduction Algorithm

1. We have a polynomial time algorithm to decide B.
   
2. Given an instance α of problem A (α is the input)
   • use a polynomial-time reduction algorithm to transform A's input α into B's input β.
     
3. Run the polynomial-time decision algorithm for B on the instance β.
   
4. Use the answer for β as the answer for α. If the answer for β is yes, the answer for α is yes.

   Example

   A = Hamiltonian cycle visits each vertex exactly once.

   B = k-cycle is a cycle of length exactly k unique vertices.

   For a graph with v vertices:

   we can answer the question: does a Hamiltonian cycle exist?

              with the question: does a cycle of length v exist?

   The answer to both questions is the same.

   Question

   1. What is the complexity of B?
   2. What is the complexity of A?
   3. What is α? What is A(α)?
   4. What is β? What is B(β)?
   5. What is the work of the reduction algorithm in this case?

Using Reduction to Show a Problem is NPC

To show no polynomial-time algorithm can exist for problem B

1. Given:
   • A is a decision problem having no polynomial-time algorithm.
   • But, a polynomial-time reduction algorithm exists for transforming instances of A into instances of B.
     
2. Proof by Contradiction:
   • Suppose that B has a polynomial-time algorithm.
   • Then using the reduction method, we could solve instances of problem A in polynomial time.
   • This contradicts our assumption that there is no polynomial-time algorithm for A.
   • Therefore, no polynomial-time algorithm can exist for problem B.

    

3. A first NP-complete problem

Reduction then relies on having a known NP-complete problem to prove a different problem NP-complete.

Need to prove a first problem NP-complete.

The First NP-Complete Problem Circuit-Satisfiability - given a Boolean circuit constructed from AND, OR and NOT gates, determine whether there is any set of Boolean inputs to the circuit that causes an output of 1. Solution - See truth table at bottom right. Question - To develop some intuition on determinism and NP-completeness, do the following on Figure (b) below: How would you solve for one output solution for x1, x2 and x3? Try to guess and verify one solution for x1, x2 and x3. Your guess is nondeterministic but the verification is deterministic. What is the worst-case complexity in determining the input to produce an output of 1? What is the complexity in verifying a given input produces an output of 1? Consider the number of operations (gates) that must be evaluated.

Figure 34.7 from Cormen

Figure 34.8 (a) and (b) from Cormen Circuit (b) = ((¬x3∧ x1∧ x2)∨¬¬x3)∧ ((x1∨x2)∧¬¬x3)∧ (¬x3∧ x1∧ x2)

x1 x2 x3 Output 0 0 0 ? 0 0 1 ? 0 1 0 ? 0 1 1 ? 1 0 0 ? 1 0 1 ? 1 1 0 1 1 1 1 ?

Solving

A brute-force solution would make all possible Boolean assignments to input variables, outputting variable assignments where true. The following would do the trick:

for x₁ ∈ {false, true} do

for x₂ ∈ {false, true} do

for x₃ ∈ {false, true} do

if ((^¬x₃∧ x₁∧ x₂)∨^¬¬x₃)∧ ((x₁∨x₂)∧^¬¬x₃)∧ (^¬x₃∧ x₁∧ x₂) then print x₁, x₂, and x₃

Complexity for n variables is Θ(2ⁿ).

 

Verifying

Given assignments to x₁, x₂, and x₃, verification can easily be done in O(n^k) or polynomial time.

if ((^¬x₃∧ x₁∧ x₂)∨^¬¬x₃)∧ ((x₁∨x₂)∧^¬¬x₃)∧ (^¬x₃∧ x₁∧ x₂) then print 1 else print 0

Executive Summary for Showing Problems to be NP-complete

1. Define problem P as a decision problem D having yes or no answer.

2. Show that any candidate solution to D can be verified in polynomial time. That makes D ∈ NP.

3. Prove an NP-complete problem, already done with Circuit-Satisfiability (CSAT).

4. Show that the input to D can be translated to CSAT input in polynomial time where CSAT answers are D answers.

5. Because solving D is now equivalent to translating D's input and solving CSAT, D must also be NP-complete.

Formally we show D ∈ NP and CSAT ≤_p D

 

Conclusion

NP - non-deterministic polynomial, can be verified in polynomial time.

decision problem - yes/no answer.

Circuit-Satisfiability has exponential (2ⁿ) complexity but can be verified in polynomial time with an answer of yes (1) or no (0).

Examples of problems in different classes

Example 1: Long simple paths.

A simple path in a graph is just one without any repeated edges or vertices. To describe the problem of finding long paths in terms of complexity theory, we need to formalize it as a yes-or-no question: given a graph G, vertices s and t, and a number k, does there exist a simple path from s to t with at least k edges? A solution to this problem would then consist of such a path.

Why is this in NP? If you're given a path, you can quickly look at it and add up the length, double-checking that it really is a path 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 unless you know a good way for finding such a path (with time polynomial in m,n, and K). And in fact this problem is NP-complete, so we believe that no such algorithm exists.

There are algorithms that solve the problem; for instance, list all 2^m subsets of edges and check whether any of them solves the problem. But as far as we know there is no algorithm that runs in polynomial time.

Example 2: Cryptography.

Suppose we have an encryption function e.g.

    code=RSA(key,text)

The "RSA" encryption works by performing some simple integer arithmetic on the code and the key, which consists of a pair (p,q) of large prime numbers. One can perform the encryption only knowing the product pq; but to decrypt the code you instead need to know a different product, (p-1)(q-1).

A standard assumption in cryptography is the "known plaintext attack": we have the code for some message, and we know (or can guess) the text of that message. We want to use that information to discover the key, so we can decrypt other messages sent using the same key.

Formalized as an NP problem, we simply want to find a key for which code=RSA(key,text). If you're given a key, you can test it by doing the encryption yourself, so this is in NP.

The hard question is, how do you find the key? For the code to be strong we hope it isn't possible to do much better than a brute force search.

Another common use of RSA involves "public key cryptography": a user 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 user by using the RSA encryption, but only the user can decrypt it. Breaking this scheme can also be thought of as a different NP problem: given a composite number pq, find a factorization into smaller numbers.

One can test a factorization quickly (just multiply the factors back together again), so the problem is in NP. Finding a factorization seems to be difficult, and we think it may not be in P. However there is some strong evidence that it is not NP-complete either; it seems to be one of the (very rare) examples of problems between P and NP-complete in difficulty.

Example 3: Chess.

There was a match between the world chess champion, 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 sequences of possible moves form a tree: The first player has a choice of 20 different moves (most of which are not very good), after each of which the second player has a choice of many responses, and so on. Chess playing programs work by traversing this tree finding what the possible consequences would be of each different move.

The tree of moves is not very deep -- a typical chess game might last 40 moves, and it is rare for one to reach 200 moves. Since each move involves a step by each player, there are at most 400 positions involved in most games. If we traversed the tree of chess positions only to that depth, we would only need enough memory to store the 400 positions on a single path at a time. This much memory is easily available on the smallest computers you are likely to use.

So perfect chess playing is a problem in PSPACE. (Actually one must be more careful in definitions. There is only a finite number of positions in chess, so in principle you could write down the solution 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 in practice is that the tree of moves is very bushy, so that even though it is not deep it has an enormous number of vertices. We won't run out of space if we try to traverse it, but we will run out of time before we get even a small fraction of the way through. Some pruning methods, notably "alpha-beta search" can help reduce the portion of the tree that needs to be examined, but not enough to solve this difficulty. For this reason, actual chess programs instead only search a much smaller depth (such as up to 7 moves), at which point they don't have enough information to evaluate the true consequences of the moves and are forced to guess by using heuristic "evaluation functions" that measure simple quantities such as the total number of pieces left.

Example 4: Halting problem.

Suppose you're working on a lab for a programming class, have written your program, and start to run it. After five minutes, it is still going. Does this mean it's in an infinite loop, or is it just slow?

It would be convenient if your compiler could tell you that your program has an infinite loop. However this is an undecidable problem: there is no program that will always correctly detect infinite loops.

Some people have used this idea as evidence that people are inherently smarter than computers, since it shows that there are problems computers can't solve. However it's not clear to me that people 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. Does it halt? (You can assume I'm using a multiple-precision integer package instead of built in integers, so don't worry about arithmetic overflow complications.) To be able to answer this, you have to understand the recent proof of Fermat's last theorem. There are many similar problems for which no proof is known, so we are clueless 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, should it also be easy to find the solution?

We have no reason to believe it should be true, so the expectation among most theoreticians is that it's false. But we also don't have a proof...

So we have this nice construction of complexity classes P and NP but 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 any particular problem is to solve?

NP-completeness

The theory of NP-completeness is a solution to the practical problem of applying complexity theory to individual problems. NP-complete problems are defined in a precise sense as the hardest problems in P. Even though we don't know whether there is any problem in NP that is not in P, we can point to an NP-complete problem and say that if there are any hard problems in NP, that problems is one of the hard ones.

(Conversely if everything in NP is easy, those problems are easy. So NP-completeness can be thought of as a way of making the big P=NP question equivalent to smaller questions about the hardness of individual problems.)

So if we believe that P and NP are unequal, and we prove that some problem is NP-complete, we should believe that it doesn't have a fast algorithm.

For unknown reasons, most problems we've looked at in NP turn out either to be in P or NP-complete. So the theory of NP-completeness turns out to be a good way of showing that a problem is likely to be hard, because it applies to a lot of problems. But there are problems that are in NP, not known to be in P, and not likely to be NP-complete; for instance the code-breaking example I gave earlier.

Reduction

Formally, NP-completeness is defined in terms of "reduction" which is just a complicated way of saying one problem is easier than another.

We say that A is easier than B, and write A < B, if we can write down an algorithm for solving A that uses a small number of calls to a subroutine for B (with everything outside the subroutine calls being fast, polynomial time). There are several minor variations of this definition depending on the detailed meaning of "small" -- it may be a polynomial number of calls, a fixed constant number, or just one call.

Then if A < B, and B is in P, so is A: we can write down a polynomial algorithm for A by expanding the subroutine calls to use the fast algorithm for B.

So "easier" in this context means that if one problem can be solved in polynomial time, so can the other. It is possible for the algorithms for A to be slower than those for B, even though A < B.

As an example, consider the Hamiltonian cycle problem. Does a given graph have a cycle visiting each vertex exactly once? Here's a 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 no

This algorithm makes m calls to a longest path subroutine, and does O(m) work outside those subroutine calls, so it shows that Hamiltonian cycle < longest path. (It doesn't show that Hamiltonian cycle is in P, because we don't know how to solve the longest path subproblems quickly.)

As a second example, consider a polynomial time problem such as the minimum spanning tree. Then for every other problem B, B < minimum spanning tree, since there is a fast algorithm for minimum spanning trees using a subroutine for B. (We don't actually have to call 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 a problem A in NP is NP-complete when, for every other problem B in NP, B < A.

This seems like a very strong definition. After all, the notion of reduction we've defined above seems to imply that if B < A, then the two problems are very closely related; for instance Hamiltonian cycle and longest path are both about finding very similar structures in graphs. Why should there be a problem that closely 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 found by modifying the halting problem (which without modification is undecidable).

Bounded halting. This problem takes as input a program X and a number K. The problem is to find data which, when given as input to X, causes it to stop in at most K steps.

To be precise, this needs some more careful definition: what language is X written in? What constitutes a single step? Also for technical reasons K should be specified in unary notation, so that the length of that part of the input is K itself rather than O(log K).

For reasonable ways of filling in the details, this is in NP: to test if data is a correct solution, just simulate the program for K steps. This takes time polynomial in K and in the length of program. (Here's one point at which we need to be careful: the program can not perform unreasonable operations such as arithmetic on very large integers, because then we wouldn't be able to simulate it quickly enough.)

To finish the proof that this is NP-complete, we need to show that it's harder than anything else in NP. Suppose we have a problem A in NP. This means that we can write a program PA that tests solutions to A, and halts within polynomial time p(n) with a yes or no answer depending on whether the given solution is really a solution to the given problem. We can then easily form a modified program PA' to enter an infinite loop whenever it would halt with a no answer. If we could solve bounded halting, we could solve A by passing PA' and p(n) as arguments to a subroutine for bounded halting. So A < bounded halting. But this argument works for every 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 for the theory of NP-completeness, but doesn't help us understand other more abstract problems such as the Hamiltonian cycle problem.

Most proofs of NP-completeness don't look like the one above; it would 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 of the existence of an algorithm that calls subroutines. Given an algorithm that solves A with a subroutine for B, and an algorithm that solves B with a subroutine for C, we can just use the second algorithm 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 is in NP, and A < B, B is NP-complete. In practice that's how we prove NP-completeness: We start with one specific problem that we prove NP-complete, and we then prove that it's easier than lots of others which must therefore also be NP-complete.

So e.g. since Hamiltonian cycle is known to be NP-complete, and Hamiltonian cycle < longest path, we can deduce that longest path is also NP-complete.

Starting from the bounded halting problem we can show that it's reducible to a problem of simulating circuits (we know that computers can be built out of circuits, so any problem involving simulating computers can be translated to one about simulating circuits). So various circuit simulation problems are NP-complete, in particular Satisfiability, which asks whether there is an input to a Boolean circuit that causes its output to be one.

Circuits look a lot like graphs, so from there it's another easy step to proving that many graph problems are NP-complete. Most of these proofs rely on constructing gadgets, small subgraphs that 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, and listed in the bible of the subject:

Computers and Intractability:
A guide to the theory of NP-completeness
Michael R. Garey and David S. Johnson
W. H. Freeman, 1979.

If you suspect a problem you're looking at is NP-complete, the first step is to look for it in Garey and Johnson. The second step is to find as similar a problem as you can in Garey and Johnson, and prove a reduction showing that similar problem to be easier than the one you want to solve. If neither of these works, you could always go back to the methods described in the rest of this class, and try to find an efficient algorithm...