Before we discuss NP-complete problems, it will be instructive to find whether there are incomputable problems. After all, the existence of such problems creates an inherent limitation in computers in terms of computability. While our argument in the previous section does not really demonstrate a concrete incomputable problem, we shall encounter one incomputable problem in this section: the famous Halting Problem.

The Halting Problem was first formulated by Alan Turing, one of the pioneers of computer science, at the time he proposed his model of computation: the Turing machine. This problem actually came as a shock, since it was first conjectured that for every function there exists an algorithm — it is just a matter of when we discover it. We define the Halting Problem, calling it HALT, as follows:

          Problem:        HALT

          Input:           Program A and an input I for A

          Output:         1 if A terminates on input I, 0 otherwise

Now, why is this problem incomputable? After all, can’t we just write a program that simulates A on input I and outputs whatever A outputs? This is not the case; for if the input program A does not terminate, then neither will the program that simulates it — failing to compute HALT. I shall only mention that this problem is simply incomputable. However, the readers should be aware that this non-trivial result can be rigorously proved using some diagonalization arguments. Such a proof has been nicely done by, for example, Sipser (1997).

 

Even if we restrict our attention exclusively to computable problems, there may still be prob­lems that require significant amounts of time to compute. We shall see some in this section. But, first, how do we determine if a problem is hard? How can we tell whether an algorithm performs well? Do we just plug in an input, run the algorithm, and count how many seconds before it terminates? To answer these questions, we shall discuss some techniques to measure the efficiency of algorithms. Two important complexity classes, P and NP, will then be introduced. After that we shall encounter the famous open question of P vs. NP and discuss some recent progress toward answering this question. Then we will see a number of ways of attacking NP-complete problems. Finally, I shall end this section by mentioning some impacts of the question of P vs. NP in practical life.

Asymptotic analysis of algorithms

Computer scientists have developed a general way of measuring the efficiency (i.e., the time complexity or the running time) of an algorithm without actually running the algorithm on some inputs. After all, we want to have an efficiency measure of an algorithm independent of the computers on which we run it. We use a technique called asymptotic analysis, first introduced for analyzing the time complexity of an algorithm by renowned computer scientist Donald Knuth. Basically, this technique tries to mimic how fast the time, which an algorithm uses to solve a problem, grows with the size of its input using some mathematical functions. However, if we were to analyze it in a precise manner, then undoubtedly the functions could be very complicated. This is when asymptotic analysis becomes useful.

In particular, asymptotic analysis provides a means of approximating complicated functions using some very simple functions. For example, suppose that we have algorithms A and B whose running times are, respectively, 1000n² and 2ⁿ where n is the size (length) of the input strings. Although the algorithm B runs faster than A does for small n, the algorithm A clearly outperforms B for large n. To make this notion more precise, we need the following definitions:

Definition 1 (The “big-O notation”): Let f and g be two functions f, g : N → N. We say that f(n) = O(g(n)) if there exists positive constants c and n₀ such that for all n > n₀, f(n) → cg(n). We say that g is an upper bound for f. Equivalently, we also say that f is of order g. See Figure 1.

Figure 1 . An illustration of the big-O notation. Here, we have f(n) = O(g(n)), and g(n) = Ω(f(n)). We say that the growth of function g(n) is asymptotically faster than the grown of function f(n). That is, after n0, g(n) is always greater than f(n).

 

Definition 2 (The “big-omega notation”): Let f and g be two functions as above. We say that f(n) = Ω(g(n)) if g(n) = O(f(n)). We say that g is a lower bound for f.

In essence, these notations give us a way of saying that some function f is bounded from above (or below) by some function g. One thing to note is that the constant of a function is immaterial in an asymptotic analysis. For instance, 1000n² and 100000n² are both of order 2. As another example, we have 10000000 = O(1).

Moreover, these notations allow us to disregards terms of smaller order. Consider the function f(n) = 1000n² + 4n³ + 8n as an example. Clearly, n³ dominates the growth rate of this function for large n, and, thus, we say that f(n) = O(n³). One last example: the function O(n⁴) + O(n) + O(2ⁿ) is of order 2ⁿ . We also write this O(n⁴) + O(n) + O(2ⁿ)= O(2ⁿ). All these can be shown with some rigorous arguments starting from the definition. Here are some simple, but useful, functions that we can use for approximating complicated functions:

          f(n) = 1: a constant function. As we saw before, for any positive constant c,

          we have c = O(1).

          f(n) = log(n): a logarithmic function.

          f(n) = n: a linear function.

          f(n) = n²: a quadratic function.

          f(n) = n^k: a polynomial function.

          f(n) = 2ⁿ : an exponential function.

          f(n) = n! : a factorial function.

How does this measure relate to real computers? Table 1 shows how long it takes for algorithms whose time complexity is f(n) to carry out a task (on a computer on which each operation takes 10^-9 seconds). We see that, to begin with, when n = 10, all of these algorithms take about the same amount of time. However, for n = 20, the algorithms whose time complexity is O(n!) become impractical, meaning it takes quite a few years before it finishes. For n > 40, the algorithm whose running time is O(2ⁿ) becomes impractical. Well before n = 50, the value of n! exceeds the number of atoms in the universe: 10⁷⁰ (Gershenfeld 2000).

Table 1 .

There are some handy facts to know when analyzing algorithms. First, arithmetic opera­tions (+, −, ×, /) can be executed in constant time (i.e., they require O(1) steps). Second, comparison operators also require constant time. Third, an algorithm spends most of its time repeating the same behavior with different parameters (i.e., looping using the For or While statements).

Equipped with this knowledge, let us now try analyzing the time complexity of the algo­rithm A that computes the EVEN algorithm introduced above. Step 1 requires constant time, since divisions can be done in constant time. Outputting 1 or 0 can also be done in constant time. Hence, the algorithm A runs in O(1) + O(1) = O(1) time. Note that the algorithm A has no looping statement.

Now, let us turn our attention to analyzing the algorithm B that computes PRIME. Steps 1 and 4 require constant time. The algorithm repeats step 3 n times. Hence, steps 2 and 3 take O(n) time. In total, the algorithm takes O(n) time. Recall that the complexity of an algorithm is expressed in terms of the size of its input. Let m be the size of the input n. Since n is represented in binary digits in computers, m is the length of the input string n in binary form, which is logarithmic in n. More precisely, m = log₂(n) and so n = 2^m. So, B indeed runs in time O(2^m). Note that a similar argument also shows that B runs in time Ω(2^m).

Complexity theorists have shown that an algorithm whose running time is O(n^k) for k constant (a polynomial-time algorithm) is strictly more efficient than one whose running time is Ω(2ⁿ) (an exponential-time algorithm). But what if the number k in the function O(n^k) is large, e.g., 1000? Then the algorithm becomes impractical. However, once there is a polynomial-time algorithm for a given problem, a significant insight into the problem is gained and usually faster algorithms (algorithms with running time O(n^k) for small k) follow.

The Complexity Class P

The complexity class P is defined to be the set of decision problems for which there exists a polynomial-time algorithm. Said differently, P is the class of decision problems that computers can compute efficiently.

From our analysis of the algorithm A, for example, we see that EVEN is in P (is efficient). On the other hand, our analysis of the algorithm B does not show that PRIME is in P (neither does it show that PRIME is not in P) since B runs in exponential time. Recently, Agrawal et al. (2002) showed that PRIME is in P — a nontrivial result that has spawned massive interests in theoretical computer science.

Another interesting problem in P is the following problem from graph theory, called PATH (see Appendix A for a discussion of graph theory).

          Problem:        PATH

          Input:           Graph G = (V, E) and two vertices u, v in V

          Output:         1 if there is a path connecting u and v in G, 0 otherwise

Observe that, in practice, PATH may be used to model the problem of determining whether there exists a sequence of flights that can take passenger from an airport a to an airport b. Now, to show that PATH is in P, we need to give a polynomial-time algorithm that computes it. The following simple algorithm C computes PATH:

          C = “On input G = (V, E) and u, v:

          1. Mark the vertex u.

          2. Repeat until the following marks no additional vertices:

                   3. Scan all edges in E. If an edge (a, b) is found where a is marked

                     and b unmarked, then mark b.

          4. Output 1 if v is marked and 0 otherwise.”

It is not hard to see that this algorithm computes PATH. Now, analyzing its complexity, we see that the bottleneck computation is located in steps 2 and 3. The time spent here is bounded above by the number of edges in G which is O(n²) where n = |V| is the size of the input. Hence, this algorithm runs in time O(n²). So, PATH is in P.

The Complexity Class NP

The class NP is the set of computable decision problems for which the answer "yes,” accompa­nied by an evidence for the answer, called a witness, can always be verified in polynomial-time. To get a feel for the concept of witness, observe that there are many problems (in particular, puzzles) in life for which it seems very hard to find an answer; but, once a “witness” is provided, it seems trivial to check the answer.

It is a fact that P NP (Sipser 1997). For example, PATH is in NP. That is, given an input <G, u, v> for PATH, a witness for <G, u, v> P NP PATH is basically a path P in G connecting the two vertices u and v. That P is indeed such a path can be verified in polynomial time. Basically, the verifier needs to check that every edge in P is a valid edge in G and that P actually connects u and v. The running time of this algorithm is bounded from above by the number of edges in G, which is in the worst case O(n²) where n = |V|.

A real-world example of NP problems is the channel assignment problem, which is currently a heavily researched topic (e.g., Roberts 1991; Griggs and Yeh 1992; Whittlesey et al. 1995; Chang and Kuo 1996; Bodlaender et al. 2000). As is the case with many combinatorial problems, this problem is quite simple to state. Given a set of transmitters x₁, ..., x_n in a region, one wishes to assign a channel (frequency) f(x_i) for the transmitter x_i for 1 < i < n such that interference is avoided as much as possible. This problem often arises in radio telecommunication.

We shall now study a particular graph-theoretic model of this problem called the L(2,1)-labeling problem. The region in the problem directly translates to a graph G whose vertices are the transmitters x₁, ..., x_n. We say that two vertices x_i, x_j, interfere if the distance between x_i and x_j is at most two. A channel assignment f is a function mapping x₁, ..., x_n to a set of natural numbers corresponding to channels such that, for any two vertices x, y, we have | f(x) − f(y) | > 1 if x and y are adjacent and | f(x) − f(y) | > 2 if x and y are a distance two apart. We define the span of f, denoted span(f), to be the difference between the maximum and the minimum channels used in f. Also, f is said to be optimal for a graph G if there is no channel assignment f ’ such that span(f ’) < span(f). The channel assignment problem CAP is defined as follows:

          Problem:        CAP
          Input:           Graph G = (V, E)
          Output:         An optimal channel assignment for G

Figure 2 illustrates a sample input and output to CAP. Clearly, CAP is not a decision problem; it is actually called an optimization problem since it attempts to optimize a function. Therefore, to show that CAP is in NP, we need to reformulate this as a decision problem. Given a graph G, let l(G) be the minimum span taken over all possible channel assignment appropriate for G. Now, we may translate CAP to the following decision problem CAP(D) as follows:

          Problem:        CAP(D)
          Input:           Graph G = (V, E)
          Output:         1 if l(G) < |V|, 0 otherwise

Figure 2. An optimal channel assignment f for a cycle with six vertices. The numbers next to the vertices correspond to channels. Here, span(f) = 4.

 

First, observe that CAP(D) is no harder than CAP; if there is a polynomial-time algorithm for CAP, then there is also a polynomial-time algorithm for CAP(D) (indeed, this argument generalizes to any optimization problem). That is, by showing that CAP(D) is hard, we also show CAP is hard. (We shall discuss what is hard in the next section.) Now, to show that CAP(D) is in NP, we need to show that CAP(D) is computable and that, given a witness for an input G =(V, E), we can check if G CAP(D) in polynomial-time. It can be shown that l(G) < (n² − n) where n = |V| (Chang and Kuo 1996). So, we can basically enumerate every possible function f : V(G) →{0, . . ., n² − n} and output 1 if there is a channel assignment f with span(f) < |V|(or output 0 otherwise). Since the number of such functions is finite, CAP(D) is computable. If, instead, G P NP CAP(D), a witness for it is simply a valid channel assignment that satisfies l(G) < |V|. Also, we can verify this in polynomial-time (since the verifier is similar to that of PATH). Hence, CAP(D) is in NP.

Now, I shall illustrate another problem of a slightly different flavor. Recall the exam time­tabling problem referenced in the Introduction. The problem is to assign a time slot to each final exam, while minimizing the exam period. Moreover, since some students may take more than one courses in a given semester but only one exam during any given time slot, some possible conflicts may arise.

We start by discussing a graph-theoretic model of this problem. How do we translate the problem to the language of graph theory? First, let the set V(G) of vertices in the graph G be the set of final exams. For any two final exams u, v in V(G), we draw an edge (u, v) P NP E(G) if and only if there is a student who will be sitting in both exams u and v. Now the problem reduces to the problem of vertex-coloring (or graph-coloring): we wish to assign a color (time slot) to each vertex such that no two adjacent vertices receive the same color. It is easy to see that these two problems are equivalent. Now, let c(G) be the smallest number of colors needed to color G such that no two adjacent vertices receive the same color. Then the exam timetabling problem EXAM can be stated as follows:

          Problem:        EXAM

          Input:           Graph G representing final exams and conflicts

          Output:         An optimal coloring for G and the number c(G)

See Figure 3 for a sample input and output to EXAM. Of course, as before, EXAM is not a decision problem. At this stage, the reader may enjoy devising a decision problem corresponding to EXAM and show that, like CAP(D), it is NP.

Figure 3. A sample conflict graph G. Vertices of G are the exams to be scheduled in a given semester (typically, in a real university setting, there can be 500 exams per semester). Edges represent conflict. Colors represent time slots. Here, we have χ(G) = 3.

P vs. NP: The Million-Dollar Question

We have just shown that CAP(D) is in NP, but is CAP(D) in P? Surprisingly, this question is equivalent to the famous open question mentioned in the Introduction. This is because CAP(D) belongs to a special complexity class: NP-complete. To define the notion of NP-completeness, we need the definitions of NP-hardness and polynomial-time reductions. Given two decision problems, P₁ and P₂, we say that P₁ is polynomial-time reducible to P₂ if there is a polynomial-time algorithm T such that, for every input i_P1 of P₁, T modifies i_P1 to an input i_P2 of P₂ in such a way that i_P1 P NP P₁ if and only if i_P2 P NP P₂. A problem P₁ is said to be NP-hard if every problem P₂ in P is polynomial-time reducible to P₁. Lastly, a problem P is said to be NP-complete if P is in NP and P is NP-hard (recall that P is a specific problem, whereas P is the complexity class of decisions problems). I shall only mention that there are numerous practical problems, such as the channel assignment problem and the exam timetabling problem, living in the NP-complete class. It is nontrivial to show that a problem is NP-hard. See Sipser (1997) for some proofs of NP-hardness.

It is not hard to check that P = NP if and only if there is an NP-complete problem P which is in P. This fact surprises many researchers because, to show that P = NP, we need to find barely one NP-complete problem in P. For this reason, most researchers believe that P NP (Gasarch 2002). Another reason supporting the conjecture that P ¹NP is that proving a statement seems much harder than verifying it. However, history has witnessed that our intuition is often dead wrong. Can you, for example, devise a polynomial-time algorithm for CAP(D)? Note that the enumeration scheme given above is exponential. The conjectured geography of the class NP is depicted in Figure 4.

Figure 4. The geography of the conjectured relationships between P, NP, and NP-complete (NPC). No one yet knows if P = NP.

There are many approaches computer scientists have taken to prove that P NP. One approach is to study circuit complexity. Boolean circuits are computational models similar to our personal computers (Sipser 1997; Papadimitriou 1994). Razborov and Rudich (1997) introduced the notion of natural proofs within which most current proofs of circuit lower bound complexity fall. Their paper suggests that natural proofs are unlikely to be useful in proving P NP. So, the challenge is to develop an unnatural proof technique. Mulmuley and Sohoni (2001) developed an approach using algebraic geometry that they think does not have the limitations of natural proofs. Another approach is to study finite model theory, a theory that stems from mathematical logic. This approach has already borne some important results (see Immerman 1997 for a detailed discussion).

Can we solve NP-complete problems?

Once we have shown that our problem is NP-complete, we know that a polynomial-time algorithm for our problem is unlikely to exist. However, this should not stop us from trying to solve our problem. What options exist? First, we may be lucky to notice that our problem has some practical easy-to-solve special cases. For example, we can restrict the inputs of CAP to cycles C_n for all positive integers n; call this new problem CAP_C. Griggs and Yeh (1992) give a simple polynomial-time algorithm for CAP_C.

Another approach is to devise a polynomial-time approximation algorithm for our problem. As opposed to trying to find an optimal solution to a problem, approximation algorithms seek a nearly optimal solution, i.e., one within a guaranteed factor of the optimal. For example, we have a polynomial-time approximation algorithm for EXAM that produces a coloring using at most D number of colors, where D is the maximum degree of any vertices in the given graph (Vazirani 2001).

Yet another approach is to develop new (physically realizable) models of computation. Quantum computing (Nielson and Chuang 2000; see O’Dwyer 2001 for overview) and DNA computing (see Srivastava 2003 for overview) are two promising such models. For example, there is a polynomial-time quantum algorithm for the problem of factoring a composite number, for which no polynomial-time algorithm on our classical model of computation is known. Also, there exist a certain number of DNA-based models of computation that can solve NP-complete problems in polynomial time (Beigel and Fu 1998). However, the physical realization of these models of computation is still uncertain at this stage due to our inability to control, respectively, quantum bits and molecules at a large scale.

Consequences of P vs. NP

Why do we — engineers, economists, scientists, philosophers, or anyone who uses technology — need to care about this question? It turns out that there are some profound consequences to the P vs. NP question. Here are just a small number of consequences:

1. If P = NP, there is no digital privacy. Today, many encryption schemes rely heavily on the assumption of the existence of a one-way function. Loosely speaking, a one-way function f : X →Y is a one-to-one function such that, for any x X, f(x) can be computed in polynomial-time and that x cannot be computed in polynomial-time given only f(x). For example, the famous RSA function is one that takes two prime numbers x and y and multiplies them to obtain xy. As noted before, multiplying two integers can be done efficiently; however, is it feasible to compute x and y given xy? This is called the factoring problem. Until today, there is no polynomial-time algorithm known for this problem. Indeed, it can be shown that there is no one-way function, unless P ( NP (Papadimitriou 1994). This implies that if P = NP, our digital domain is insecure.

2. If P = NP, randomness is unnecessary. Randomization has proven to be a useful tool in computer science. Many hard problems admit some very simple polynomial-time ran­domized algorithms, and yet there is no proof that they are strictly more powerful that their deterministic counterparts. That is, almost all known polynomial-time randomized algorithms can be derandomized, yielding polynomial-time deterministic algorithms. For example, computer scientists had known the existence of a simple polynomial-time ran­domized algorithm for PRIME long ago before they first discovered a polynomial-time deterministic algorithm (Sipser 1997; Papadimitriou 1994; Agrawal et al. 2002). More formally, let us define BPP to be the set of problems P for which there is a polynomial-time algorithm M that satisfies the following conditions:

          • For x P, the probability of M(x) = 1 is at least 2/3.

          • For x P, the probability of M(x) = 0 is at least 2/3.

Such an algorithm is called randomized. There are many important problems in BPP (see Papadimitriou 1994). By definition, we have P BPP. However, it is open whether BPP NP and BPP Í P. Obviously, if BPP P, then randomized algorithms gain no essential speedup over the deterministic ones. An interesting result is that if P = NP, then P = BPP (using an important result from Impagliazzo and Wigderson 1997).

3. If P NP, mathematicians and practitioners will be greatly aided by computers. As we noted before, many important practical problems are NP-complete. More often than not, this implies that a large subclass of any NP-complete problem requires a creative solution that can only be produced by creative thinkers, which are human. This implies that a large part of our creative thinking cannot be replaced by computers unless P = NP.

4. Nonapproximability unless P = NP. As mentioned previously, one option of attacking NP-complete problems is to devise a well-behaved approximation algorithm. Unfortu­nately, this is not always possible for a large class of NP-hard optimization problems unless P = NP (see Papadimitriou 1994; Vazirani 2001).