📄 chap36.htm
字号:
<HTML><HEAD>
<TITLE>Intro to Algorithms: CHAPTER 36: NPCOMPLETENESS</TITLE></HEAD><BODY BGCOLOR="#FFFFFF">
<a href="chap37.htm"><img align=right src="../../images/next.gif" alt="Next Chapter" border=0></A>
<a href="toc.htm"><img align=right src="../../images/toc.gif" alt="Return to Table of Contents" border=0></A>
<a href="chap35.htm"><img align=right src="../../images/prev.gif" alt="Previous Chapter" border=0></A>
<h1><a name="09f9_1c6f">CHAPTER 36: NP-COMPLETENESS<a name="09f9_1c6f"></h1><P>
<a name="09f9_1c67"><a name="09f9_1c68"><a name="09f9_1c69"><a name="09f9_1c6a"><a name="09f9_1c6b"><a name="09f9_1c6c"><a name="09f9_1c6d"><a name="09f9_1c6e">All of the algorithms we have studied thus far have been <I><B>polynomial-time</I></B> <I><B>algorithms</I></B>: on inputs of size <I>n</I>, their worst-case running time is <I>O</I>(<I>n<SUP>k</I></SUP>) for some constant <I>k</I>. It is natural to wonder whether <I>all</I> 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 <I>O</I>(<I>n<SUP>k</I></SUP>) for any constant <I>k</I>. Generally, we think of problems that are solvable by polynomial-time algorithms as being tractable, and problems that require superpolynomial time as being intractable.<P>
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 a superpolynomial-time lower bound for any of them. This so-called P <img src="../images/noteq.gif"> NP question has been one of the deepest, most perplexing open research problems in theoretical computer science since it was posed in 1971.<P>
Most theoretical computer scientists believe that the NP-complete problems are intractable. The reason is that if any single NP-complete problem can be solved in polynomial time, then <I>every</I> NP-complete problem has a polynomial-time algorithm. Given the wide range of NP-complete problems that have been studied to date, without any progress toward a polynomial-time solution, it would be truly astounding if all of them could be solved in polynomial time.<P>
To become a good algorithm designer, you must understand the rudiments of the theory of NP-completeness. If you can establish a problem as NP-complete, you provide good evidence for its intractability. As an engineer, you would then do better spending your time developing an approximation algorithm (see Chapter 37) rather than searching for a fast algorithm that solves the problem exactly. Moreover, many natural and interesting problems that on the surface seem no harder than sorting, graph searching, or network flow are in fact NP-complete. Thus, it is important to become familiar with this remarkable class of problems.<P>
This chapter studies the aspects of NP-completeness that bear most directly on the analysis of algorithms. In Section 36.1, we formalize our notion of "problem" and define the complexity class P of polynomial-time solvable decision problems. We also see how these notions fit into the framework of formal-language theory. Section 36.2 defines the class NP of decision problems whose solutions can be verified in polynomial time. It also formally poses the P <img src="../images/noteq.gif"> NP question.<P>
Section 36.3 shows how relationships between problems can be studied via polynomial-time "reductions." It defines NP-completeness and sketches a proof that one problem, called "circuit satisfiability," is NP-complete. Having found one NP-complete problem, we show in Section 36.4 how other problems can be proven to be NP-complete much more simply by the methodology of reductions. The methodology is illustrated by showing that two formula-satisfiability problems are NP-complete. A variety of other problems are shown to be NP-complete in Section 36.5.<P>
<h1><a name="09fb_0001">36.1 Polynomial time<a name="09fb_0001"></h1><P>
We begin our study of NP-completeness by formalizing our notion of polynomial-time solvable problems. These problems are generally regarded as tractable. The reason why is a philosophical, not a mathematical, issue. We can offer three supporting arguments.<P>
First, although it is reasonable to regard a problem that requires time <img src="../images/bound.gif">(<I>n</I><SUP>100</SUP>) as intractable, there are very few practical problems that require time on the order of such a high-degree polynomial. The polynomial-time computable problems encountered in practice typically require much less time.<P>
Second, for many reasonable models of computation, a problem that can be solved in polynomial time in one model can be solved in polynomial time in another. For example, the class of problems solvable in polynomial time by the serial random-access machine used throughout most of this book is the same as the class of problems solvable in polynomial time on abstract Turing machines.<SUP>1 </SUP>It is also the same as the class of problems solvable in polynomial time on a parallel computer, even if the number of processors grows polynomially with the input size.<P>
<SUP>1</SUP>See Hopcroft and Ullman [104] or Lewis and Papadimitriou [139] for a thorough treatment of the Turing-machine model. of calls to polynomial-time subroutines, the running time of the composite algorithm is polynomial.<P>
Third, the class of polynomial-time solvable problems has nice closure properties, since polynomials are closed under addition, multiplication, and composition. For example, if the output of one polynomial-time algorithm is fed into the input of another, the composite algorithm is polynomial. If an otherwise polynomial-time algorithm makes a constant number of calls to polynomial-time subroutines, the running time of the composite algorithm is polynomial.<P>
<h2>Abstract problems</h2><P>
<a name="09fc_1c6f"><a name="09fc_1c70"><a name="09fc_1c71"><a name="09fc_1c72"><a name="09fc_1c73"><a name="09fc_1c74">To understand the class of polynomial-time solvable problems, we must first have a formal notion of what a "problem" is. We define an <I><B>abstract problem</I></B><I> Q</I> to be a binary relation on a set <I>I</I> of problem <I><B>instances</I></B> and a set <I>S </I>of problem <I><B>solutions</I></B>. For example, consider the problem SHORTEST-PATH of finding a shortest path between two given vertices in an unweighted, undirected graph <I>G =</I> (<I>V, E</I>). An instance for SHORTEST-PATH is a triple consisting of a graph and two vertices. A solution is a sequence of vertices in the graph, with perhaps the empty sequence denoting that no path exists. The problem SHORTEST-PATH itself is the relation that associates each instance of a graph and two vertices with a shortest path in the graph that connects the two vertices. Since shortest paths are not necessarily unique, a given problem instance may have more than one solution.<P>
<a name="09fc_1c75"><a name="09fc_1c76">This formulation of an abstract problem is more general than is required for our purposes. For simplicity, the theory of NP-completeness restricts attention to<B> </B><I><B>decision problems</I></B>: those having a yes/no solution. In this case, we can view an abstract decision problem as a function that maps the instance set <I>I</I> to the solution set {0, 1}. For example, a decision problem PATH related to the shortest-path problem is, "Given a graph <I>G = </I>(<I>V, E</I>), two vertices <I>u, v </I><img src="../images/memof12.gif"> <I>V</I>, and a nonnegative integer <I>k</I>, does a path exist in <I>G</I> between <I>u</I> and <I>v</I> whose length is at most <I>k</I>?" If <I>i</I> = <<I>G, u, v, k</I>> is an instance of this shortest-path problem, then PATH(<I>i</I>) = 1 (yes) if a shortest path from <I>u</I> to <I>v</I> has length at most <I>k</I>, and PATH(<I>i</I>) = 0 (no) otherwise.<P>
<a name="09fc_1c77"><a name="09fc_1c78">Many abstract problems are not decision problems, but rather <I><B>optimization problems</I></B>, in which some value must be minimized or maximized. In order to apply the theory of NP-completeness to optimization problems, we must recast them as decision problems. Typically, an optimization problem can be recast by imposing a bound on the value to be optimized. As an example, in recasting the shortest-path problem as the decision problem PATH, we added a bound <I>k</I> to the problem instance.<P>
Although the theory of NP-completeness compels us to recast optimization problems as decision problems, this requirement does not diminish the impact of the theory. In general, if we can solve an optimization problem quickly, we can also solve its related decision problem quickly. We simply compare the value obtained from the solution of the optimization problem with the bound provided as input to the decision problem. If an optimization problem is easy, therefore, its related decision problem is easy as well. Stated in a way that has more relevance to NP-completeness, if we can provide evidence that a decision problem is hard, we also provide evidence that its related optimization problem is hard. Thus, even though it restricts attention to decision problems, the theory of NP-completeness applies much more widely.<P>
<P>
<h2>Encodings</h2><P>
<a name="09fd_1c79">If a computer program is to solve an abstract problem, problem instances must must be represented in a way that the program understands. An <I><B>encoding</I> </B>of a set <I>S</I> of abstract objects is a mapping <I>e</I> from <I>S</I> to the set of binary strings.<SUP>2 </SUP>For example, we are all familiar with encoding the natural numbers <I>N</I> = {0, 1, 2, 3, 4, . . .} as the strings {0, 1, 10, 11, 100, . . .}. Using this encoding, <I>e</I>(l7) = 10001. Anyone who has looked at computer representations of keyboard characters is familiar with either the ASCII or EBCDIC codes. In the ASCII code, <I>e</I>(<FONT FACE="Courier New" SIZE=2>A</FONT>) = 1000001. Even a compound object can be encoded as a binary string by combining the representations of its constituent parts. Polygons, graphs, functions, ordered pairs, programs--all can be encoded as binary strings.<P>
<SUP>2 </SUP>The codomain of <I>e</I> need not be <I>binary</I> strings; any set of strings over a finite alphabet having at least 2 symbols will do.<P>
<a name="09fd_1c7a"><a name="09fd_1c7b"><a name="09fd_1c7c"><a name="09fd_1c7d"><a name="09fd_1c7e">Thus, a computer algorithm that "solves" some abstract decision problem actually takes an encoding of a problem instance as input. We call a problem whose instance set is the set of binary strings a <I><B>concrete problem</I></B>. We say that an algorithm <I><B>solves </I></B>a concrete problem in time <I>O</I>(<I>T</I>(<I>n</I>)) if, when it is provided a problem instance<I> i</I> of length <I>n</I> = |<I>i|</I>, the algorithm can produce the solution in at most <I>O</I>(<I>T</I>(<I>n</I>)) time. A concrete problem is <I><B>polynomial-time solvable</I></B>, therefore, if there exists an algorithm to solve it in time <I>O</I>(<I>n<SUP>k</I></SUP>) for some constant <I>k</I>.<P>
<a name="09fd_1c7f"><a name="09fd_1c80">We can now formally define the <I><B>complexity class</I> P</B> as the set of concrete decision problems that are solvable in polynomial time.<P>
We can use encodings to map abstract problems to concrete problems. Given an abstract decision problem <I>Q</I> mapping an instance set <I>I</I> to {0, 1}, an encoding <I>e : I</I> <img src="../images/arrow12.gif"> {0, 1}<SUP>*</SUP> can be used to induce a related concrete decision problem, which we denote by <I>e</I>(<I>Q</I>). If the solution to an abstract-problem instance <I>i </I><img src="../images/memof12.gif"><I> </I>I<I> is </I>Q<I>(</I>i<I>) <img src="../images/memof12.gif"></I> {0, 1}, then the solution to the concrete-problem instance <I>e</I>(<I>i</I>) <img src="../images/memof12.gif"><I> </I>{0, 1}<SUP>* </SUP>is also <I>Q</I>(<I>i</I>). As a technicality, there may be some binary strings that represent no meaningful abstract-problem instance. For convenience, we shall assume that any such string is mapped arbitrarily to 0. Thus, the concrete problem produces the same solutions as the abstract problem on binary-string instances that represent the encodings of abstract-problem instances.<P>
<a name="09fd_1c81">We would like to extend the definition of polynomial-time solvability from concrete problems to abstract problems using encodings as the bridge, but we would like the definition to be independent of any particular encoding. That is, the efficiency of solving a problem should not depend on how the problem is encoded. Unfortunately, it depends quite heavily. For example, suppose that an integer <I>k</I> is to be provided as the sole input to an algorithm, and suppose that the running time of the algorithm is <img src="../images/bound.gif">(<I>k</I>). If the integer <I>k</I> is provided in <I><B>unary</I></B>--a string of <I>k</I> 1's--then the running time of the algorithm is <I>O</I>(<I>n</I>) on length-<I>n</I> inputs, which is polynomial time. If we use the more natural binary representation of the integer <I>k</I>, however, then the input length is <I>n</I> = <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrul14.gif"></FONT>lg <I>k<FONT FACE="Courier New" SIZE=2></I><img src="../images/hfbrur14.gif"><I></I>.</FONT> In this case, the running time of the algorithm is <img src="../images/bound.gif">(<I>k</I>) = <img src="../images/bound.gif">(2<I><SUP>n</I></SUP>), which is exponential in the size of the input. Thus, depending on the encoding, the algorithm runs in either polynomial or superpolynomial time.<P>
The encoding of an abstract problem is therefore quite important to our understanding of polynomial time. We cannot really talk about solving an abstract problem without first specifying an encoding. Nevertheless, in practice, if we rule out "expensive" encodings such as unary ones, the actual encoding of a problem makes little difference to whether the problem can be solved in polynomial time. For example, representing integers in base 3 instead of binary has no effect on whether a problem is solvable in polynomial time, since an integer represented in base 3 can be converted to an integer represented in base 2 in polynomial time.<P>
<a name="09fd_1c82"><a name="09fd_1c83">We say that a function <I>f </I>: {0, 1}<SUP>* </SUP><img src="../images/arrow12.gif"> {0, 1}<SUP>*</SUP> is <I><B>polynomial-time computable</I></B> if there exists a polynomial-time algorithm <I>A</I> that, given any input <I>x</I> <img src="../images/memof12.gif"> {0, 1}<SUP>*</SUP>, produces as output <I>f</I>(<I>x</I>). For some set <I>I</I> of problem instances, we say that two encodings <I>e</I><SUB> </SUB> and <I>e</I><SUB> </SUB> are <I><B>polynomially related</I></B> if there exist two polynomial-time computable functions <I>f</I><SUB>12</SUB> and <I>f</I><SUB>21</SUB> such that for any <I>i </I><img src="../images/memof12.gif"><I> I</I>, we have <I>f</I><SUB>12</SUB>(<I>e</I><SUB>1</SUB>(<I>i</I>)) = <I>e</I><SUB>2</SUB>(<I>i</I>) and <I>f</I><SUB>21</SUB>(<I>e</I><SUB>2</SUB>(<I>i</I>)) = <I>e</I><SUB>1</SUB>(<I>i</I>). That is, the encoding <I>e</I><SUB>2</SUB>(<I>i</I>) can be computed from the encoding <I>e</I><SUB>1</SUB>(<I>i</I>) by a polynomial-time algorithm, and vice versa. If two encodings <I>e</I><SUB>1</SUB> and <I>e</I><SUB>2</SUB> of an abstract problem are polynomially related, which we use makes no difference to whether the problem is polynomial-time solvable or not, as the following lemma shows.<P>
<a name="09fd_1c84">Lemma 36.1<a name="09fd_1c84"><P>
Let <I>Q</I> be an abstract decision problem on an instance set <I>I</I>, and let <I>e</I><SUB>1</SUB> and <I>e</I><SUB>2</SUB> be polynomially related encodings on <I>I</I>. Then, <I>e</I><SUB>1</SUB>(<I>Q</I>) <img src="../images/memof12.gif"> P if and only if <I>e</I><SUB>2</SUB>(<I>Q</I>) <img src="../images/memof12.gif"> P.<P>
<I><B>Proof</I></B><I> </I>We need only prove the forward direction, since the backward direction is symmetric. Suppose, therefore, that <I>e</I><SUB>1</SUB>(<I>Q</I>) can be solved in time <I>O</I>(<I>n<SUP>k</I></SUP>) for some constant <I>k</I>. Further, suppose that for any problem instance <I>i</I>, the encoding <I>e<SUB>1</I></SUB>(<I>i</I>) can be computed from the encoding <I>e</I><SUB>2</SUB>(<I>i</I>) in time <I>O</I>(<I>n<SUP>c</I></SUP>) for some constant <I>c</I>, where <I>n</I> = |<I>e</I><SUB>1</SUB>(<I>i</I>)|. To solve problem <I>e</I><SUB>2</SUB>(<I>Q</I>), on input <I>e</I><SUB>2</SUB>(<I>i</I>), we first compute <I>e</I><SUB>1</SUB>(<I>i</I>) and then run the algorithm for <I>e</I><SUB>1</SUB>(<I>Q</I>) on <I>e</I><SUB>1</SUB>(<I>i</I>). How long does this take? The conversion of encodings takes time <I>O</I>(<I>n<SUP>c</I></SUP>), and therefore |<I>e</I><SUB>1</SUB>(<I>i</I>)| = <I>O</I>(<I>n<SUP>c</I></SUP>), since the output of a serial computer cannot be longer than its running time. Solving the problem on <I>e</I><SUB>1</SUB> (<I>i</I>) takes time <I>O</I>(<I>|e</I><SUB>1</SUB>(<I>i</I>)|<I><SUP>k</I></SUP>) = <I>O</I>(<I>n<SUP>ck</I></SUP>), which is polynomial since both <I>c</I> and <I>k</I> are constants. <P>
Thus, whether an abstract problem has its instances encoded in binary or base 3 does not affect its "complexity," that is, whether it is polynomial-time solvable or not, but if instances are encoded in unary, its complexity may change. In order to be able to converse in an encoding-independent fashion, we shall generally assume that problem instances are encoded in any reasonable, concise fashion, unless we specifically say otherwise. To be precise, we shall assume that the encoding of an integer is polynomially related to its binary representation, and that the encoding of a finite set is polynomially related to its encoding as a list of its elements, enclosed in braces and separated by commas. (ASCII is one such encoding scheme.) With such a "standard" encoding in hand, we can derive reasonable encodings of other mathematical objects, such as tuples, graphs, and formulas. To denote the standard encoding of an object, we shall enclose the object in angle braces. Thus, <img src="../images/lftwdchv.gif"><I>G</I><img src="../images/wdrtchv.gif"> denotes the standard encoding of a graph <I>G</I>.<P>
As long as we implicitly use an encoding that is polynomially related to this standard encoding, we can talk directly about abstract problems without reference to any particular encoding, knowing that the choice of encoding has no effect on whether the abstract problem is polynomial-time solvable. Henceforth, we shall generally assume that all problem instances are binary strings encoded using the standard encoding, unless we explicitly specify the contrary. We shall also typically neglect the distinction between abstract and concrete problems. The reader should watch out for problems that arise in practice, however, in which a standard encoding is not obvious and the encoding does make a difference.<P>
<P>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -