chap36.htm

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

<h2><a name="0a04_1cb8">Exercises<a name="0a04_1cb8"></h2><P>
<a name="0a04_1cb9">36.2-1<a name="0a04_1cb9"><P>
<a name="0a04_1caf"><a name="0a04_1cb0">Consider the language GRAPH-ISOMORPHISM = {<img src="../images/lftwdchv.gif"><I>G</I><SUB>1</SUB>, <I>G</I><SUB>2</SUB><img src="../images/wdrtchv.gif"> : <I>G</I><SUB>1</SUB> and <I>G</I><SUB>2 </SUB>are isomorphic graphs}. Prove that GRAPH-ISOMORPHISM <img src="../images/memof12.gif"> NP by describing a polynomial-time algorithm to verify the language.<P>
<a name="0a04_1cba">36.2-2<a name="0a04_1cba"><P>
Prove that if <I>G</I> is an undirected bipartite graph with an odd number of vertices, then <I>G</I> is nonhamiltonian.<P>
<a name="0a04_1cbb">36.2-3<a name="0a04_1cbb"><P>
Show that if HAM-CYCLE <img src="../images/memof12.gif"> P, then the problem of listing the vertices of a hamiltonian cycle, in order, is polynomial-time solvable.<P>
<a name="0a04_1cbc">36.2-4<a name="0a04_1cbc"><P>
Prove that the class NP of languages is closed under union, intersection, concatenation, and Kleene star. Discuss the closure of NP under complement.<P>
<a name="0a04_1cbd">36.2-5<a name="0a04_1cbd"><P>
Show that any language in NP can be decided by an algorithm running in time 2<I><SUP>O</I>(<I>nk</I>)</SUP> for some constant <I>k</I>.<P>
<a name="0a04_1cbe">36.2-6<a name="0a04_1cbe"><P>
<a name="0a04_1cb1"><a name="0a04_1cb2"><a name="0a04_1cb3"><a name="0a04_1cb4"><a name="0a04_1cb5">A <I><B>hamiltonian path</I> </B>in a graph is a simple path that visits every vertex exactly once. Show that the language HAM-PATH = {<img src="../images/lftwdchv.gif"><I>G, u, v</I><img src="../images/wdrtchv.gif"> : there is a hamiltonian path from <I>u</I> to <I>v</I> in graph <I>G</I>} belongs to NP.<P>
<a name="0a04_1cbf">36.2-7<a name="0a04_1cbf"><P>
Show that the hamiltonian-path problem can be solved in polynomial time on directed acyclic graphs. Give an efficient algorithm for the problem.<P>
<a name="0a04_1cc0">36.2-8<a name="0a04_1cc0"><P>
<a name="0a04_1cb6"><a name="0a04_1cb7">Let <img src="../images/phicap12.gif"><I></I> be a boolean formula constructed from the boolean input variables <I>x</I><SUB>1</SUB>, <I>x</I><SUB>2</SUB>, . . . , <I>x<SUB>k</I></SUB>, negations (<img src="../images/rtdwnbrc.gif">), AND's (<img src="../images/angleup.gif">), OR's (<img src="../images/angledwn.gif">), and parentheses. The formula <img src="../images/phicap12.gif"><I></I> is a <I><B>tautology</I></B> if it evaluates to 1 for every assignment of 1 and 0 to the input variables. Define TAUTOLOGY as the language of boolean formulas that are tautologies. Show that TAUTOLOGY <img src="../images/memof12.gif"> co-NP.<P>
<a name="0a04_1cc1">36.2-9<a name="0a04_1cc1"><P>
Prove that P <img src="../images/rgtubar.gif"> co-NP.<P>
<a name="0a04_1cc2">36.2-10<a name="0a04_1cc2"><P>
Prove that if NP <img src="../images/noteq.gif"> co-NP, then P <img src="../images/noteq.gif"> NP.<P>
<a name="0a04_1cc3">36.2-11<a name="0a04_1cc3"><P>
Let <I>G</I> be a connected, undirected graph with at least 3 vertices, and let <I>G</I><SUP>3 </SUP>be the graph obtained by connecting all pairs of vertices that are connected by a path in <I>G</I> of length at most 3. Prove that <I>G</I><SUP>3</SUP> is hamiltonian. (<I>Hint</I>: Construct a spanning tree for <I>G</I>, and use an inductive argument.)<P>
<P>


<P>







<h1><a name="0a05_0001">36.3 NP-completeness and reducibility<a name="0a05_0001"></h1><P>
Perhaps the most compelling reason why theoretical computer scientists believe that P <img src="../images/noteq.gif"> NP is the existence of the class of "NP-complete" problems. This class has the surprising property that if any <I>one</I> NP-complete problem can be solved in polynomial time, then <I>every</I> problem in NP has a polynomial-time solution, that is, P = NP. Despite years of study, though, no polynomial-time algorithm has ever been discovered for any NP-complete problem.<P>
The language HAM-CYCLE is one NP-complete problem. If we could decide HAM-CYCLE in polynomial time, then we could solve every problem in NP in polynomial time. In fact, if NP - P should turn out to be nonempty, we could say with certainty that HAM-CYCLE <img src="../images/memof12.gif"> NP - P.<P>
<img src="930_a.gif"><P>
<h4><a name="0a05_0002">Figure 36.3 An illustration of a polynomial-time reduction from a language L<SUB>1</SUB> to a language L<SUB>2</SUB> via a reduction function f. For any input x <img src="../images/memof12.gif"> {0, 1}*, the question of whether x <img src="../images/memof12.gif"> L<SUB>1</SUB> has the same answer as the question of whether f(x) <img src="../images/memof12.gif"> L<SUB>2</SUB><FONT FACE="Times New Roman" SIZE=2>.<a name="0a05_0002"></FONT></sub></sup></h4><P>
The NP-complete languages are, in a sense, the "hardest" languages in NP. In this section, we shall show how to compare the relative "hardness" of languages using a precise notion called "polynomial-time reducibility." First, we formally define the NP-complete languages, and then we sketch a proof that one such language, called CIRCUIT-SAT, is NP-complete. In Section 36.5, shall use the notion of reducibility to show that many other problems are NP-complete.<P>





<h2>Reducibility</h2><P>
<a name="0a06_1cb8">Intuitively, a problem <I>Q</I> can be reduced to another problem <I>Q</I>' if any instance of <I>Q</I> can be "easily rephrased" as an instance of <I>Q</I>', the solution to which provides a solution to the instance of <I>Q</I>. For example, the problem of solving linear equations in an indeterminate <I>x</I> reduces to the problem of solving quadratic equations. Given an instance <I>ax</I> + <I>b</I> = 0, we transform it to 0<I>x</I><SUP>2</SUP> + <I>ax</I> + <I>b</I> = 0, whose solution provides a solution to <I>ax</I> + <I>b</I> = 0. Thus, if a problem <I>Q</I> reduces to another problem <I>Q</I>', then <I>Q</I> is, in a sense, "no harder to solve" than <I>Q</I>'.<P>
<a name="0a06_1cb9"><a name="0a06_1cba">Returning to our formal-language framework for decision problems, we say that a language <I>L</I><SUB>1</SUB> is <I><B>polynomial-time reducible</I></B> to a language <I>L</I><SUB>2</SUB>, written <I>L</I><SUB>1</SUB> <img src="../images/lteq12.gif"><SUB>P</SUB> <I>L</I><SUB>2</SUB>, if there exists a polynomial-time computable function <I>f </I>: {0, 1}* <img src="../images/arrow12.gif"> {0, 1}* such that for all <I>x</I> <img src="../images/memof12.gif"> {0, 1}*,<P>
<pre><I>x</I> <img src="../images/memof12.gif"> <I>L</I><SUB>1 </SUB>if and only if <I>f</I>(<I>x</I>) <img src="../images/memof12.gif"> <I>L</I><SUB>2</SUB> .</sub></sup></pre><P>
<h4><a name="0a06_1cbd">(36.1)<a name="0a06_1cbd"></sub></sup></h4><P>
<a name="0a06_1cbb"><a name="0a06_1cbc">We call the function <I>f</I> the <I><B>reduction function</I></B>, and a polynomial-time algorithm <I>F</I> that computes <I>f</I> is called a<B> </B><I><B>reduction algorithm</I></B><I>.</I><P>
Figure 36.3 illustrates the idea of a polynomial-time reduction from a language <I>L</I><SUB>1</SUB> to another language <I>L</I><SUB>2</SUB>. Each language is a subset of {0, 1}*. The reduction function <I>f</I> provides a polynomial-time mapping such that if <I>x</I> <img src="../images/memof12.gif"> <I>L</I><SUB>1</SUB>, then <I>f</I>(<I>x</I>) <img src="../images/memof12.gif"> <I>L</I><SUB>2</SUB>. Moreover, if <I>x</I> <img src="../images/notmem.gif"> <I>L</I><SUB>1</SUB>, then <I>f</I>(<I>x</I>) <img src="../images/notmem.gif"> <I>L</I><SUB>2</SUB>. Thus, the reduction function maps any instance <I>x</I> of the decision problem represented by the language <I>L</I><SUB>1</SUB> to an instance <I>f</I>(<I>x</I>) of the problem represented by <I>L</I><SUB>2</SUB>. Providing an answer to whether <I>f</I>(<I>x</I>) <img src="../images/memof12.gif"> <I>L</I><SUB>2</SUB> directly provides the answer to whether <I>x</I> <img src="../images/memof12.gif"> <I>L</I><SUB>1</SUB>.<P>
<img src="931_a.gif"><P>
<h4><a name="0a06_1cbe">Figure 36.4 The proof of Lemma 36.3. The algorithm F is a reduction algorithm that computes the reduction function f from L<SUB>1</SUB> to L<SUB>2</SUB> in polynomial time, and A<SUB>2 </SUB>is a polynomial-time algorithm that decides L<SUB>2</SUB>. Illustrated is an algorithm A<SUB>1</SUB> that decides whether x <img src="../images/memof12.gif"> L<SUB>1</SUB> by using F to transform any input x into f(x) and then using A<SUB>2</SUB> to decide whether f(x) <img src="../images/memof12.gif"> L<SUB>2</SUB><FONT FACE="Times New Roman" SIZE=2>.<a name="0a06_1cbe"></FONT></sub></sup></h4><P>
Polynomial-time reductions give us a powerful tool for proving that various languages belong to P.<P>
<a name="0a06_1cbf">Lemma 36.3<a name="0a06_1cbf"><P>
If <I>L</I><SUB>1</SUB>, <I>L</I><SUB>2</SUB> <img src="../images/rgtubar.gif"> {0, 1}<SUP>*</SUP> are languages such that <I>L</I><SUB>1</SUB> <img src="../images/lteq12.gif"> <I>L</I><SUB>2</SUB>, then <I>L</I><SUB>2</SUB> <img src="../images/memof12.gif"> P implies <I>L</I><SUB>1</SUB> <img src="../images/memof12.gif"> P.<P>
<I><B>Proof</I></B>     Let <I>A</I><SUB>2</SUB> be a polynomial-time algorithm that decides <I>L</I><SUB>2</SUB>, and let <I>F</I> be a polynomial-time reduction algorithm that computes the reduction function <I>f</I>. We shall construct a polynomial-time algorithm <I>A</I><SUB>1</SUB> that decides <I>L</I><SUB>1</SUB>.<P>
Figure 36.4 illustrates the construction of <I>A</I><SUB>1</SUB>. For a given input <I>x</I> <img src="../images/memof12.gif"> {0, 1}*, the algorithm <I>A</I><SUB>1</SUB> uses <I>F</I> to transform <I>x</I> into <I>f</I>(<I>x</I>), and then it uses <I>A</I><SUB>2</SUB> to test whether <I>f</I>(<I>x</I>) <img src="../images/memof12.gif"> <I>L</I><SUB>2</SUB>. The output of <I>A</I><SUB>2</SUB> is the value provided as the output from <I>A</I><SUB>1</SUB>.<P>