chap36.htm

美国麻省理工的算法导论,英文版,看后程序员宏观的能力培养有好处

<h1><a name="0a00_1ca0">36.2 Polynomial-time verification<a name="0a00_1ca0"></h1><P>
<a name="0a00_1c9e"><a name="0a00_1c9f">We now look at algorithms that "verify" membership in languages. For example, suppose that for a given instance <img src="../images/lftwdchv.gif"><I>G, u, v, k</I><img src="../images/wdrtchv.gif"> of the decision problem PATH, we are also given a path <I>p</I> from <I>u</I> to <I>v</I>. We can easily check whether the length of <I>p</I> is at most <I>k</I>, and if so, we can view <I>p</I> as a "certificate" that the instance indeed belongs to PATH. For the decision problem PATH, this certificate doesn't seem to buy us much. After all, PATH belongs to P--in fact, PATH can be solved in linear time--and so verifying membership from a given certificate takes as long as solving the problem from scratch. We shall now examine a problem for which we know of no polynomial-time decision algorithm yet, given a certificate, verification is easy.<P>
<img src="925_a.gif"><P>
<h4><a name="0a00_1ca1">Figure 36.1 (a) A graph representing the vertices, edges, and faces of a dodecahedron, with a hamiltonian cycle shown by shaded edges. (b) A bipartite graph with an odd number of vertices. Any such graph is nonhamiltonian.<a name="0a00_1ca1"></sub></sup></h4><P>





<h2>Hamiltonian cycles</h2><P>
<a name="0a01_1ca0"><a name="0a01_1ca1"><a name="0a01_1ca2"><a name="0a01_1ca3"><a name="0a01_1ca4"><a name="0a01_1ca5">The problem of finding a hamiltonian cycle in an undirected graph has been studied for over a hundred years. Formally, a <I><B>hamiltonian cycle</I></B> of an undirected graph <I>G</I> = (<I>V, E</I>) is a simple cycle that contains each vertex in <I>V</I>. A graph that contains a hamiltonian cycle is said to be <I><B>hamiltonian; </I></B>otherwise, it is<I><B> nonhamiltonian.</I></B> Bondy and Murty [31] cite a letter by W. R. Hamilton describing a mathematical game on the dodecahedron (Figure 36.1(a)) in which one player sticks five pins in any five consecutive vertices and the other player must complete the path to form a cycle containing all the vertices. The dodecahedron is hamiltonian, and Figure 36.1 (a) shows one hamiltonian cycle. Not all graphs are hamiltonian, however. For example, Figure 36.1 (b) shows a bipartite graph with an odd number of vertices. (Exercise 36.2-2 asks you to show that all such graphs are nonhamiltonian.)<P>
<a name="0a01_1ca6">We can define the <I><B>hamiltonian-cycle problem,</I></B> "Does a graph <I>G</I> have a hamiltonian cycle?" as a formal language:<P>
<pre><a name="0a01_1ca7">HAM-CYCLE = {<img src="../images/lftwdchv.gif"><I>G</I><img src="../images/wdrtchv.gif"><I> : G</I> is a hamiltonian graph}<I> .</I></sub></sup></pre><P>
How might an algorithm decide the language HAM-CYCLE? Given a problem instance<I> </I><img src="../images/lftwdchv.gif"><I>G</I><img src="../images/wdrtchv.gif">, one possible decision algorithm lists all permutations of the vertices of <I>G</I> and then checks each permutation to see if it is a hamiltonian path. What is the running time of this algorithm? If we use the "reasonable" encoding of a graph as its adjacency matrix, the number <I>m</I> of vertices in the graph is <img src="926_a.gif"> , where <I>n</I> = |<img src="../images/lftwdchv.gif"><I>G</I><img src="../images/wdrtchv.gif">| is the length of the encoding of <I>G</I>. There are <I>m</I>! possible permutations of the vertices, and therefore the running time is <img src="926_b.gif">, which is not <I>O</I>(<I>n<SUP>k</I></SUP>) for any constant <I>k</I>. Thus, this naive algorithm does not run in polynomial time, and in fact, the hamiltonian-cycle problem is NP-complete, as we shall prove in Section 36.5.<P>
<P>







<h2>Verification algorithms</h2><P>
Consider a slightly easier problem, however. Suppose that a friend tells you that a given graph <I>G</I> is hamiltonian, and then offers to prove it by giving you the vertices in order along the hamiltonian cycle. It would certainly be easy enough to verify the proof: simply verify that the provided cycle is hamiltonian by checking whether it is a permutation of the vertices of <I>V</I> and whether each of the consecutive edges along the cycle actually exists in the graph. This verification algorithm can certainly be implemented to run in <I>O</I>(<I>n<SUP>2</I></SUP>) time, where <I>n</I> is the length of the encoding of <I>G</I> . Thus, a proof that a hamiltonian cycle exists in a graph can be verified in polynomial time.<P>
<a name="0a02_1ca8"><a name="0a02_1ca9">We define a <I><B>verification algorithm </I></B>as being a two-argument algorithm <I>A<B>, </I></B>where one argument is an ordinary input string <I>x </I>and the other is a binary string <I>y </I>called a <I><B>certificate</I></B>. A two-argument algorithm<I><B> </I></B><I>A<B> verifies </I></B>an input string <I>x </I>if there exists a certificate<I> y</I> such that <I>A</I>(<I>x, y</I>) = 1. The <I><B>language verified</I></B> by a verification algorithm<B> </B><I>A</I> is<P>
<pre><I>L</I> = {<I>x</I> <img src="../images/memof12.gif"> {0, 1}* : there exists <I>y</I> <img src="../images/memof12.gif">{0, 1}* such that <I>A</I>(<I>x, y</I>) = 1} .</sub></sup></pre><P>
Intuitively, an algorithm <I>A</I> verifies a language <I>L</I> if for any string <I>x</I> <img src="../images/memof12.gif"> <I>L</I>, there is a certificate <I>y</I> that A can use to prove that <I>x</I> <img src="../images/memof12.gif"> <I>L</I>. Moreover, for any string <I>x</I> <img src="../images/notmem.gif"> <I>L</I> there must be no certificate proving that <I>x</I> <img src="../images/memof12.gif"> <I>L.</I> For example, in the hamiltonian-cycle problem, the certificate is the list of vertices in the hamiltonian cycle. If a graph is hamiltonian, the hamiltonian cycle itself offers enough information to verify this fact. Conversely, if a graph is not hamiltonian, there is no list of vertices that can fool the verification algorithm into believing that the graph is hamiltonian, since the verification algorithm carefully checks the proposed "cycle" to be sure.<P>
<P>







<h2>The complexity class NP</h2><P>
<a name="0a03_1caa"><a name="0a03_1cab">The <I><B>complexity class</I> NP</B> is the class of languages that can be verified by a polynomial-time algorithm.<SUP>3 </SUP>More precisely, a language <I>L</I> belongs to NP if and only if there exists a two-input polynomial-time algorithm <I>A</I> and constant <I>c</I> such that<P>
<pre><I>L</I> = {<I>x</I> <img src="../images/memof12.gif"> {0,1}* : there exists a certificate <I>y</I> with |<I>y</I>| = <I>0</I>(|<I>x</I>|<I><SUP>c</I></SUP>)</sub></sup></pre><P>
<pre>such that <I>A</I>(<I>x,y</I>) = 1} .</sub></sup></pre><P>
We say that algorithm <I>A</I> <I><B>verifies</I></B> language <I>L</I> <I><B>in polynomial time</I></B><I>.</I><P>
<a name="0a03_1cac"><SUP>3</SUP>The name "NP" stands for "nondeterministic polynomial time." The class NP was originally studied in the context of nondeterminism, but this book uses the somewhat simpler yet equivalent notion of verification. Hopcroft and Ullman [104] give a good presentation of NP-completeness in terms of nondeterministic models of computation.<P>
From our earlier discussion on the hamiltonian-cycle problem, it follows that HAM-CYCLE <img src="../images/memof12.gif"> NP. (It is always nice to know that an important set is nonempty.) Moreover, if <I>L</I> <img src="../images/memof12.gif"> P, then <I>L</I> <img src="../images/memof12.gif"> NP, since if there is a polynomial-time algorithm to decide <I>L</I>, the algorithm can be easily converted to a two-argument verification algorithm that simply ignores any certificate and accepts exactly those input strings it determines to be in <I>L</I>. Thus, P <img src="../images/rgtubar.gif"> NP.<P>
It is unknown whether P = NP, but most researchers believe that P and NP are not the same class. Intuitively, the class P consists of problems that can be solved quickly. The class NP consists of problems for which a solution can be verified quickly. You may have learned from experience that it is often more difficult to solve a problem from scratch than to verify a clearly presented solution, especially when working under time constraints. Theoretical computer scientists generally believe that this analogy extends to the classes P and NP, and thus that NP includes languages that are not in P.<P>
There is more compelling evidence that P <img src="../images/noteq.gif"> NP--the existence of "NP-complete" languages. We shall study this class in Section 36.3.<P>
<a name="0a03_1cad"><a name="0a03_1cae">Many other fundamental questions beyond the P <img src="../images/noteq.gif"> NP question remain unresolved. Despite much work by many researchers, no one even knows if the class NP is closed under complement. That is, does <I>L</I> <img src="../images/memof12.gif"> NP imply <img src="927_a.gif">? We can define the <I><B>complexity class</I> co-NP</B> as the set of languages <I>L</I> such that <img src="927_b.gif">. The question of whether NP is closed under complement can be rephrased as whether NP = co-NP. Since P is closed under complement (Exercise 36.1-7), it follows that P <img src="../images/rgtubar.gif"> NP <img src="../images/dome.gif"> co-NP. Once again, however, it is not known whether P = NP <img src="../images/dome.gif"> co-NP or whether there is some language in NP <img src="../images/dome.gif"> co-NP - P. Figure 36.2 shows the four possible scenarios.<P>
Thus, our understanding of the precise relationship between P and NP is woefully incomplete. Nevertheless, by exploring the theory of NP-completeness, we shall find that our disadvantage in proving problems to be intractable is, from a practical point of view, not nearly so great as we might suppose.<P>
<img src="928_a.gif"><P>
<h4><a name="0a03_1caf">Figure 36.2 Four possibilities for relationships among complexity classes. In each diagram, one region enclosing another indicates a proper-subset relation. (a) P = NP = co-NP. Most researchers regard this possibility as the most unlikely. (b) If NP is closed under complement, then NP = co-NP, but it need not be the case that P = NP. (c) P = NP <img src="../images/dome.gif"> co-NP, but NP is not closed under complement. (d) NP <img src="../images/noteq.gif"> co-NP and P <img src="../images/noteq.gif"> NP <img src="../images/dome.gif"> co-NP. Most researchers regard this possibility as the most likely.<a name="0a03_1caf"></sub></sup></h4><P>
<P>