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