chap36.htm

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

The correctness of <I>A</I><SUB>1</SUB> follows from condition (36.1). The algorithm runs in polynomial time, since both <I>F</I> and <I>A</I><SUB>2</SUB> run in polynomial time (see Exercise 36.1-6).      <P>
<P>







<h2>NP-completeness</h2><P>
<a name="0a07_1cbd">Polynomial-time reductions provide a formal means for showing that one problem is at least as hard as another, to within a polynomial-time factor. That is, if <I>L</I><SUB>1</SUB> <img src="../images/lteq12.gif"><SUB>p</SUB> <I>L</I><SUB>2</SUB>, then <I>L</I><SUB>1</SUB> is not more than a polynomial factor harder than <I>L</I><SUB>2</SUB>, which is why the "less than or equal to" notation for reduction is mnemonic. We can now define the set of NP-complete languages, which are the hardest problems in NP.<P>
A language <I>L</I> <img src="../images/rgtubar.gif"> {0, 1}<SUP>*</SUP> is <I><B>NP-complete</I></B> if<P>
1.     <I>L</I> <img src="../images/memof12.gif"> NP, and<P>
2.     <I>L</I>' <img src="../images/lteq12.gif"><SUB>p</SUB> <I>L</I> for every <I>L</I>' <img src="../images/memof12.gif"> NP.<P>
<img src="932_a.gif"><P>
<h4><a name="0a07_1cc1">Figure 36.5 How most theoretical computer scientists view the relationships among P, NP, and NPC. Both P and NPC are wholly contained within NP, and <img src="932_b.gif">.<a name="0a07_1cc1"></sub></sup></h4><P>
<a name="0a07_1cbe"><a name="0a07_1cbf"><a name="0a07_1cc0">If a language <I>L</I> satisfies property 2, but not necessarily property 1, we say that <I>L</I> is <I><B>NP-hard</I></B>. We also define NPC to be the class of NP-complete languages.<P>
As the following theorem shows, NP-completeness is at the crux of deciding whether P is in fact equal to NP.<P>
<a name="0a07_1cc2">Theorem 36.4<a name="0a07_1cc2"><P>
If any NP-complete problem is polynomial-time solvable, then P = NP. If any problem in NP is not polynomial-time solvable, then all NP-complete problems are not polynomial-time solvable.<P>
<I><B>Proof</I></B>     Suppose that <I>L</I> <img src="../images/memof12.gif"> P and also that <I>L</I> <img src="../images/memof12.gif"> NPC. For any <I>L</I>' <img src="../images/memof12.gif"> NP, we have <I>L</I>' <img src="../images/lteq12.gif"><SUB>p</SUB> <I>L</I> by property 2 of the definition of NP-completeness. Thus, by Lemma 36.3, we also have that <I>L</I>' <img src="../images/memof12.gif"> P, which proves the first statement of the lemma.<P>
To prove the second statement, suppose that there exists an <I>L</I> <img src="../images/memof12.gif"> NP such that <I>L</I> <img src="../images/notmem.gif"> P. Let <I>L</I>' <img src="../images/memof12.gif"> NPC be any NP-complete language, and for the purpose of contradiction, assume that <I>L</I>' <img src="../images/memof12.gif"> P. But then, by Lemma 36.3, we have <I>L</I> <img src="../images/lteq12.gif"><SUB>p</SUB> <I>L</I>', and thus <I>L</I> <img src="../images/memof12.gif"> P.      <P>
It is for this reason that research into the P <img src="../images/noteq.gif"> NP question centers around the NP-complete problems. Most theoretical computer scientists believe that P <img src="../images/noteq.gif"> NP, which leads to the relationships among P, NP, and NPC shown in Figure 36.5. But for all we know, someone may come up with a polynomial-time algorithm for an NP-complete problem, thus proving that P = NP. Nevertheless, since no polynomial-time algorithm for any NP-complete problem has yet been discovered, a proof that a problem is NP-compete provides excellent evidence for its intractability.<P>
<P>







<h2>Circuit satisfiability</h2><P>
<a name="0a08_1cc1"><a name="0a08_1cc2">We have defined the notion of an NP-complete problem, but up to this point, we have not actually proved that any problem is NP-complete. Once we prove that at least one problem is NP-complete, we can use polynomial-time reducibility as a tool to prove the NP-completeness of other problems. Thus, we now focus on demonstrating the existence of an NP-complete problem: the circuit-satisfiability problem.<P>
<img src="933_a.gif"><P>
<h4><a name="0a08_1cc9">Figure 36.6 Two instances of the circuit-satisfiability problem. (a) The assignment <img src="../images/lftwdchv.gif">x<SUB>1</SUB> = 1, x<SUB>2</SUB> = 1, x<SUB>3</SUB> = 0<img src="../images/wdrtchv.gif"> to the inputs of this circuit causes the output of the circuit to be 1. The circuit is therefore satisfiable. (b) No assignment to the inputs of this circuit can cause the output of the circuit to be 1. The circuit is therefore unsatisfiable.<a name="0a08_1cc9"></sub></sup></h4><P>
Unfortunately, the formal proof that the circuit-satisfiability problem is NP-complete requires technical detail beyond the scope of this text. Instead, we shall informally describe a proof that relies on a basic understanding of boolean combinational circuits. This material is reviewed at the beginning of Chapter 29.<P>
<a name="0a08_1cc3"><a name="0a08_1cc4"><a name="0a08_1cc5"><a name="0a08_1cc6"><a name="0a08_1cc7">Figure 36.6 shows two boolean combinational circuits, each with three inputs and a single output. A <I><B>truth assignment</I></B> for a boolean combinational circuit is a set of boolean input values. We say that a one-output boolean combinational circuit is <I><B>satisfiable</I></B> if it has a <I><B>satisfying assignment</I></B>: a truth assignment that causes the output of the circuit to be 1. For example, the circuit in Figure 36.6(a) has the satisfying assignment <img src="../images/lftwdchv.gif"><I>x</I><SUB>1</SUB> = 1, <I>x</I><SUB>2</SUB> = 1, <I>x</I><SUB>3</SUB> = 0<img src="../images/wdrtchv.gif">, and so it is satisfiable. No assignment of values to <I>x</I><SUB>1</SUB>, <I>x</I><SUB>2</SUB>, and <I>x</I><SUB>3</SUB> causes the circuit in Figure 36.6(b) to produce a 1 output; it always produces 0, and so it is unsatisfiable.<P>
The <I><B>circuit-satisfiability problem</I></B> is, "Given a boolean combinational circuit composed of AND, OR, and NOT gates, is it satisfiable?" In order to pose this question formally, however, we must agree on a standard encoding for circuits. One can devise a graphlike encoding that maps any given circuit <I>C</I> into a binary string <img src="../images/lftwdchv.gif"><I>C</I><img src="../images/wdrtchv.gif"> whose length is not much larger than the size of the circuit itself. As a formal language, we can therefore define<P>
<pre><a name="0a08_1cc8">CIRCUIT-SAT =</sub></sup></pre><P>
<pre>{<img src="../images/lftwdchv.gif"><I>C</I><img src="../images/wdrtchv.gif"> : <I>C</I> is a satisfiable boolean combinational circuit} .</sub></sup></pre><P>
The circuit-satisfiability problem has great importance in the area of computer-aided hardware optimization. If a circuit always produces 0, it can be replaced by a simpler circuit that omits all logic gates and provides the constant 0 value as its output. A polynomial-time algorithm for the problem would have considerable practical application.<P>
Given a circuit <I>C</I>, we might attempt to determine whether it is satisfiable by simply checking all possible assignments to the inputs. Unfortunately, if there are <I>k</I> inputs, there are 2<I><SUP>k</I></SUP> possible assignments. When the size of <I>C</I> is polynomial in <I>k</I>, checking each one leads to a superpolynomial-time algorithm. In fact, as has been claimed, there is strong evidence that no polynomial-time algorithm exists that solves the circuit-satisfiability problem because circuit satisfiability is NP-complete. We break the proof of this fact into two parts, based on the two parts of the definition of NP-completeness.<P>
<a name="0a08_1cca">Lemma 36.5<a name="0a08_1cca"><P>
The circuit-satisfiability problem belongs to the class NP.<P>
<I><B>Proof</I></B>     We shall provide a two-input, polynomial-time algorithm <I>A</I> that can verify CIRCUIT-SAT. One of the inputs to <I>A</I> is (a standard encoding of) a boolean combinational circuit <I>C</I>. The other input is a certificate corresponding to an assignment of boolean values to the wires in <I>C</I>.<P>
The algorithm <I>A</I> is constructed as follows. For each logic gate in the circuit, it checks that the value provided by the certificate on the output wire is correctly computed as a function of the values on the input wires. Then, if the output of the entire circuit is 1, the algorithm outputs 1, since the values assigned to the inputs of <I>C</I> provide a satisfying assignment. Otherwise, <I>A</I> outputs 0.<P>
Whenever a satisfiable circuit <I>C</I> is input to algorithm <I>A</I>, there is a certificate whose length is polynomial in the size of <I>C</I> and that causes <I>A</I> to output a 1. Whenever an unsatisfiable circuit is input, no certificate can fool <I>A </I>into believing that the circuit is satisfiable. Algorithm <I>A</I> runs in polynomial time: with a good implementation, linear time suffices. Thus, CIRCUIT-SAT can be verified in polynomial time, and CIRCUIT-SAT <img src="../images/memof12.gif"> NP.      <P>
The second part of proving that CIRCUIT-SAT is NP-complete is to show that the language is NP-hard. That is, we must show that every language in NP is polynomial-time reducible to CIRCUIT-SAT. The actual proof of this fact is full of technical intricacies, and so we shall settle for a sketch of the proof based on some understanding of the workings of computer hardware.<P>
A computer program is stored in the computer memory as a sequence of instructions. A typical instruction encodes an operation to be performed, addresses of operands in memory, and an address where the result is to be stored. A special memory location, called the <I><B>program counter</I></B>, keeps track of which instruction is to be executed next. The program counter is automatically incremented whenever an instruction is fetched, thereby causing the computer to execute instructions sequentially. The execution of an instruction can cause a value to be written to the program counter, however, and then the normal sequential execution can be altered, allowing the computer to loop and perform conditional branches.<P>
At any point during the execution of a program, the entire state of the computation is represented in the computer's memory. (We take the memory to include the program itself, the program counter, working storage, and any of the various bits of state that a computer maintains for bookkeeping.) We call any particular state of computer memory a <I><B>configuration</I></B>. The execution of an instruction can be viewed as mapping one configuration to another. Importantly, the computer hardware that accomplishes this mapping can be implemented as a boolean combinational circuit, which we denote by <I>M</I> in the proof of the following lemma.<P>
<a name="0a08_1ccb">Lemma 36.6<a name="0a08_1ccb"><P>
The circuit-satisfiability problem is NP-hard.<P>
<I><B>Proof</I></B>     Let <I>L</I> be any language in NP. We shall describe a polynomial-time algorithm <I>F</I> computing a reduction function &acirc; that maps every binary string <I>x</I> to a circuit <I>C = &acirc;</I>(<I>x</I>) such that <I>x </I><img src="../images/memof12.gif"> L<I> if and only if </I>C <I><img src="../images/memof12.gif"> </I>CIRCUIT-SAT.<P>
Since <I>L</I> <img src="../images/memof12.gif"> NP, there must exist an algorithm <I>A</I> that verifies <I>L</I> in polynomial-time. The algorithm <I>F</I> that we shall construct will use the two-input algorithm <I>A</I> to compute the reduction function &acirc;.<P>
Let <I>T</I>(<I>n</I>) denote the worst-case running time of algorithm <I>A</I> on length-<I>n </I>input strings, and let <I>k</I> <img src="../images/gteq.gif"> 1 be a constant such that <I>T</I>(<I>n</I>)<I> = O</I>(<I>n<SUP>k</I></SUP>) and the length of the certificate is <I>O</I>(<I>n<SUP>k</I></SUP>). (The running time of <I>A</I> is actually a polynomial in the total input size, which includes both an input string and a certificate, but since the length of the certificate is polynomial in the length <I>n</I> of the input string, the running time is polynomial in <I>n</I>.)<P>
The basic idea of the proof is to represent the computation of <I>A</I> as a sequence of configurations. As shown in Figure 36.7, each configuration can be broken into parts consisting of the program for <I>A</I>, the program counter and auxiliary machine state, the input <I>x</I>, the certificate <I>y</I>, and working storage. Starting with an initial configuration <I>c</I><SUB>0</SUB>, each configuration <I>c<SUB>i</I></SUB> is mapped to a subsequent configuration <I>c<SUB>i+</I>1</SUB> by the combinational circuit <I>M </I>implementing the computer hardware. The output of the algorithm <I>A</I>--0 or 1--is written to some designated location in the working storage when <I>A</I> finishes executing, and if we assume that thereafter <I>A</I> halts, the value never changes. Thus, if the algorithm runs for at most <I>T</I>(<I>n</I>) steps, the output appears as one of the bits in <I>c<SUB>T</I>(<I>n</I>)</SUB>.<P>
<img src="936_a.gif"><P>
<h4><a name="0a08_1ccc">Figure 36.7 The sequence of configurations produced by an algorithm A running on an input x and certificate y. Each configuration represents the state of the computer for one step of the computation and, besides A, x, and y, includes the program counter (PC), auxiliary machine state, and working storage. Except for the certificate y, the initial configuration c<SUB>0</SUB> is constant. Each configuration is mapped to the next configuration by a boolean