|
|
< Day Day Up > |
|
Almost all the algorithms we have studied thus far have been polynomial-time algorithms: on inputs of size n, their worst-case running time is O(nk) for some constant k. It is natural to wonder whether all problems can be solved in polynomial time. The answer is no. For example, there are problems, such as Turing's famous "Halting Problem," that cannot be solved by any computer, no matter how much time is provided. There are also problems that can be solved, but not in time O(nk) for any constant k. Generally, we think of problems that are solvable by polynomial-time algorithms as being tractable, or easy, and problems that require superpolynomial time as being intractable, or hard.
The subject of this chapter, however, is an interesting class of problems, called the "NP-complete" problems, whose status is unknown. No polynomial-time algorithm has yet been discovered for an NP-complete problem, nor has anyone yet been able to prove that no polynomial-time algorithm can exist for any one of them. This so-called P ≠ NP question has been one of the deepest, most perplexing open research problems in theoretical computer science since it was first posed in 1971.
A particularly tantalizing aspect of the NP-complete problems is that several of them seem on the surface to be similar to problems that have polynomial-time algorithms. In each of the following pairs of problems, one is solvable in polynomial time and the other is NP-complete, but the difference between problems appears to be slight:
Shortest vs. longest simple paths: In Chapter 24, we saw that even with negative edge weights, we can find shortest paths from a single source in a directed graph G = (V, E) in O(V E) time. Finding the longest simple path between two vertices is NP-complete, however. In fact, it is NP-complete even if all edge weights are 1.
Euler tour vs. hamiltonian cycle: An Euler tour of a connected, directed graph G = (V, E) is a cycle that traverses each edge of G exactly once, although it may visit a vertex more than once. By Problem 22-3, we can determine whether a graph has an Euler tour in only O(E) time and, in fact, we can find the edges of the Euler tour in O(E) time. A hamiltonian cycle of a directed graph G = (V, E) is a simple cycle that contains each vertex in V . Determining whether a directed graph has a hamiltonian cycle is NP-complete. (Later in this chapter, we shall prove that determining whether an undirected graph has a hamiltonian cycle is NP-complete.)
2-CNF satisfiability vs. 3-CNF satisfiability: A boolean formula contains variables whose values are 0 or 1; boolean connectives such as ∧ (AND), ∨ (OR), and ¬ (NOT); and parentheses. A boolean formula is satisfiable if there is some assignment of the values 0 and 1 to its variables that causes it to evaluate to 1. We shall define terms more formally later in this chapter, but informally, a boolean formula is in k-conjunctive normal form, or k-CNF, if it is the AND of clauses of ORs of exactly k variables or their negations. For example, the boolean formula (x1 ∨ ¬x2) ∧ (¬x1 ∨ x3) ∧ (¬x2 ∨ ¬x3) is in 2-CNF. (It has the satisfying assignment x1 = 1, x2 = 0, x3 = 1.) There is a polynomial-time algorithm to determine whether a 2-CNF formula is satisfiable, but as we shall see later in this chapter, determining whether a 3-CNF formula is satisfiable is NP-complete.
|
|
< Day Day Up > |
|