算法分析英文完全np问题

1、Algorithms Design and Analysis pleteness: Lecture 2Prof. Dr. Jinxing XieDept. of Mathematical SciencesTsinghua University, Beijing 100084, China Voice:(86-10)62787812 Fax:(86-10)62785847However , nobody knows if NP P .In addition, it seems no hope for proving P = NP. If P NP , then Q NP - P This is

2、our main focus !P NPax+b=00 x2+ax+b=0Linear equations no harder thanQuadratic equationsReduction?Polynomial reducibilityDefinition:( polynomial reduction ) A language L1 0,1* is polynomial-time reducible to a language L2 0,1* if there exists a polynomialtime computable function f: 0,1* 0,1* For all

3、x L1 iff f(x) L2. Notation L1 P L2or L1 L2 Note: sometimes this kind of polynomial reduction is called “polynomial transformation”It is called the reduction function, And the corresponding polynomial-time algorithm F is called reduction algorithmLemma: If L1 L2 , then L2 P L1 P, and equivalently L1

4、P L2 P.proof x 0,1* , |f(x)| pF(| x|) T(|x|)=O( pf( | x| ) + p2( pF( | x | ) ) )=O(p1( | x| ) )FA2note Q1 , Q2 : decision problems L(Q1, e1) L(Q2, e2) a decision problem Q1 is polynomial reducible to a decision problem Q2 if there is a functionthat satisfies the following two conditions: (i) f is co

5、mputable by a polynomial time algorithm (ii)A Hamiltonian cycle (circuit) of an undirected (directed) graph G=(V,E) is a simple cycle (circuit) that includes all vertices of V.HC( or HAM-CYCLE: Hamiltonian Cycle ) Instance : A Graph G = ( V,E ) Question : Does G contain a Hamiltonian circuit ?TSP( T

6、raveling Salesman Problem) Instance : A finite set C = c1, c2 , , c of cities. A distance d(ci , cj ) Z+ for each pair of cities ci , cj C, and a bound B Z+. Question : Is there a tour of all cities in C having total length no more than B ?Is HC TSP ? Yes ! Why ?C := V (ci := vi)d(ci, cj ) := 1 if v

7、i, vj E 2 otherwiseB := |V| (i) f can be computable by a polynomial time algorithm why ? (ii) For all i DHC, i YHC f(i) YTSP why ? HC TSPLemma : If L1 L2 and L2 L3 , then L1 L3 (Transitive Property) proof Let 1, 2 , and 3 be the alphabets of languages L1, L2 , and L3 , respectively.f1 : 1* 2* a poly

8、nomial transformation from L1 to L2.f2 : 2* 3* a polynomial transformation from L2 to L3.Then , f3 : 1* 3* is f2(f1(x) for all x 1* . x 1* , x L1 f1(x) L2 f2( f1 (x) ) L3 x L1 f2( f1 (x) ) L3 L1 L3 f1f2xf1 (x) f2 (f1(x) | x1| (f2 * f1 )(x)= f2 ( f1 (x) f2 * f1 = f3P1 (|x1|) P2(P1 (|x1|) )Definition:

9、 Two language L1 and L2 (two decision problems Q1 and Q2 ) are said to be polynomially equivalent if L1 L2 and L2 L1 ( Q1 2 and Q2 1 ). P and plete give equivalent classes !P pleteNPDefinition: A language L is defined to be plete if (i) L NP (ii) L L for all L NP.If (ii) holds, whether (i) holds or

10、not, L is called NP-hard.NPC: the complexity class of plete languages (decision problems)NPH: the complexity class of NP-hard languages (decision problems)Lemma : If L1 and L2 belong to NP, L1 is plete, and L1 L2 then L2 is pleteGiven an plete problem Q and a new problem Q , (i) Q NP (ii) Q QQ NPCLe

11、mma : If any plete problem is polynomial-time solvable, then P=NP. or equivalently, if any problem in NP is not polynomial-time solvable, then no plete problem is polynomial-time solvable.x A yesnoyesnoA P : Given i in I, is X true for i ?Co-P : Given i in I, is X false for i ?Given a DTM algorithm

12、A for solving P , A can be used for solving Co-P ! Co-P PIs the same true for an NDTM algorithm ? Well , . h h(x)However , to answer Qc we need to examine all possible solutions !*Polynomial verifiability ( for Q)QTSP ( Traveling Salesman Problem)TSP : Given a set of cities , the intercity distance

13、and a bound B , is it true that there is a tour of all cities having total length no more than B ?Co-TSP : - , Is it true that every tour of all cities has total length more than B ?NPPCo-NPP NPObservationP Co-PCo-P P P = Co-PSuppose that P = NP.Then , NP = Co-NPWhat if P NP ?Theorem : If there exis

14、ts an plete problem such thatc NP, then NP = Co-NP. Why ?AAThe NDTM program AA accepts c NP NP = Co-NP ( NP )Yespolynomial verifiabilityCIRCUIT-SAT (circuit satisfiability ) Instance : A boolean combinational circuit C Question : Is there a satisfying truth assignment for C? (over the set U of boole

15、an inputs / boolean variables)What is a boolean combinational circuit? one or more boolean combinational elements interconnected by wiresWhat is a boolean combinational element? any circuit element that has a constant number of boolean inputs and outputs and that performs a well-defined functionThre

16、e basic boolean elements (logical gates): OR, AND, NOTThe first NPC problemTruth tableCan be easily extended to the case with multiple inputs2k possible truth assignments!k circuit inputs only 1 circuit output allowed herefan-in & fan-out must have no cycle!size of the circuit: the number of boolean

17、 combinational elements plus the number of wires in the circuitEncoding of a boolean combinational circuit: one can use graphlike (“dag”) encoding that maps any given circuit C into a binary string whose length is polynomial in the size of the circuit iteselfFormal language:CIRCUIT-SAT=: C is a sati

18、sfiable boolean combinational circuitLemma: CIRCUIT-SAT NPproofCertificate: an assignment y of boolean values to the wires in C (its length is obviously of a polynomial function of the circuit size)Verifying algorithm A: given C and y, check whether each output of a logical gate is correctly compute

19、d as a function of the input values if yes, and if the output of the entire circuit is 1, then A(C,y)=1; otherwise, A(C,y)=0.Finally, A runs in polynomial timeLemma: CIRCUIT-SAT NP-hardproofLet L be any language in LP. We should prove L CIRCUIT-SATWe should find a polynomial-time algorithm F computi

20、ng function f, for any x L iff C=f(x) CIRCUIT-SATSince L, there exists an algorithm A that verifies L in polynomial timeLet T(n) denote the worst-case running time of A on length-n inputAnd let k=1 be a constant such that T(n)=O(nk) and the length of the certificate is O(nk) PC: program counterconfi

21、gurationStarting with the initial configuration c0,each configuration ci is mapped to a subsequent configuration ci+1by the combinational circuit M implementing the computer hardwarePaste together T(n) copies of the circuit of M The output of the ith circuit (which produces configuration ci), is fed

22、 directly into the input of the (i+1)st circuitHow to Construct of F?Given an input x, F must compute a circuit C=f(x) that is satisfiable iff there is a certificate y such that A(x,y)=1. Compute n=|x|; Construct a combinational circuit C consisting of T(n) copies of M; the input to C is an initial

23、configuration corresponding to a computation on A(x,y) the output to C is the configuration cT(n)C=f(x) is modified slightly from C: the output of C is ignored except the bit of cT(n) corresponding to the output of AWhy F is enough? Given an input x, F must compute a circuit C=f(x) that is satisfiab

24、le iff there is a certificate y such that A(x,y)=1. This is true from the construction of F F runs in polynomial time in n=|x|First,the number of bits required to represent a configuration is polynomial in n.Second, the combinational circuit M implementing the computer hardware has size polynomial i

25、n the length of a configuration, which is polynomial O(nk), thus polynomial in n. This completes the proof (but its only an informal one!)Given a decision problem (language) L:Prove L NPSelect a known NPC language LDescribe an algorithm that computes a function f mapping every instance x 0,1* of L t

26、o an instance f(x) of LProve that the function f satisfies x L iff f(x) L for all x 0,1*Prove that the algorithm computing f runs in polynomial timeHow to prove L NPCLemma : If L and L belong to NP, L is plete, and L L , then L is pleteSAT (satisfiability, or formula satisfiability ) Instance : n Bo

27、olean variables and m boolean connectives. Question : Is there a satisfying truth assignment? =(x1 x2 ) x5 ) (x2 x3 ) (x7 x9 ) ) (x4 x6 ) (x1 x7 x8 x9 ). here n=9Boolean connectives: AND, OR, NOT, ,2n possible assignments!SAT=: is a satisfiable boolean formulaSATIts easy to show that SAT NP since gi

28、ven the certificate (truth assignment), whether the formula is satisfiable can be checked in polynomial time Remaining to prove: CIRCUIT-SAT SATBasic idea: simply look at the gate that produces the circuit output, and inductively express each of the gates inputs as formulasWrite an express that appl

29、ies the gates function to its inputs formulaHowever, when the output wires have fan-out of 2 or more, the size of the generated formula grows exponentially! thus this straightforward method doest work!SAT NPC= x10 (x4 x3 ) (x5 (x1 x2 ) ) (x6 x4) (x7 (x1 x2 x4 ) (x8 (x5 x6 ) ) (x9 (x6 x7 ) ) (x10 (x7

30、 x8 x9 ) For each wire xi in the circuit,There is a variable xi in the formulaThen CIRCUIT-SAT SAT3-CNF-SAT3-CNF-SAT (3-CNF-satisfiability) Instance : A set U of n Boolean variables and a collection of clauses C over U, each clause contains 3 literals. Question : Is there a satisfying truth assignme

31、nt for C ? (x1 x2 x5 ) (x2 x3 x7) (x4 x6 x9 ) ( x7 x8 x9 ). here n=9 “k-CNF”(k-conjunctive normal form): an AND of ORsU = x1 , x2 , x3 , ., x9 C = x1 , x2 , x5 ,x2 , x3 , x7 ,x4 , x6 ,x9 ,x7 , x8 , x9 Logic operations: AND, OR, NOTLiteral: a variable or its negative Clause: OR of literals2n possible

32、 assignments! “DNF”(disjunctive normal form): an OR of ANDsHow to prove 3-CNF-SAT NPCIts easy to show that 3-CNF-SAT NP (or, since 3-CNF-SAT is a special case of SAT, thus 3-CNF-SAT NP)Remaining to prove: SAT 3-CNF-SATThree steps: First, we construct a binary “parse” tree for the input formula ,With

33、 literals as leaves and connectives as internal nodes.Should the input formula contain a clause such as the OR of several literals, associative can be used to parenthesize the expression fully so that every internal node in the insulting tree has 1 or 2 children.= y1 (y1 (y2 x2 ) ) (y2 (y3 y4 ) ) (y

34、3 (x1 x2) ) (y4 y5 ) (y5 (y5 x4 ) ) (y6 ( x1 x3 ) ) Each clause i has at most 3 literals1= (y1 y2 x2 ) (y1 y2 x2 ) (y1 y2 x2 ) (y1 y2 x2 )(DNF) The second step: using truth table,convert each clause into CNFUsing DeMorgans law1= (y1 y2 x2 ) (y1 y2 x2 ) (y1 y2 x2 ) (y1 y2 x2 )(DNF) 1=1= (y1 y2 x2 ) (

35、y1 y2 x2 ) (y1 y2 x2 ) (y1 y2 x2 )(DNF) The third step: Each clause i has exactly 3 literalsCi= (l1 l2) Ci= (l1 l2 p ) (l1 l2 p ) If a clause has exactly 3 literals, OK!If a clause has exactly 2 literals: use another variable p:Ci= l Ci= (l p q ) (l p q ) (l p q ) (l p q ) If a clause has exactly 1

36、literals: use another two variables p, q:The final step: polynomial-time1st step: at most 1 variable and 1 clause per connection in 2nd step: at most 8 clauses for each clause in 1st step3nd step: at most 4 clauses for each clause in 2st stepMore NPC problemsReview of this lecture What is Polynomial

37、-time reduction? What is NPC? First NPC Problem: CIRCUIT-SAT is NPCSAT is NPC3-CNF-SAT is NPCHomeworkRead Chapter 34.3-34.4Hand-ins: 34.3-8; 34.4-3SAT (satisfiability, or formula satisfiability ) Instance : A set U of n Boolean variables and a collection of clauses C over U. Question : Is there a sa

38、tisfying truth assignment for C ? (u1 u2 u5 ) (u2 u3 u7 u9 ) (u4 u6 ) (u1 u7 u8 u9 ). here n=9 “k-CNF”(k-conjunctive normal form): an AND of ORsU = u1 , u2 , u3 , ., u9 C = u1 , u2 , u5 ,u2 , u3 , u7 , u9 ,u4 , u6 ,u1 , u7 , u8 , u9 Logic operations: AND, OR, NOTLiteral: a variable or its negative C

39、lause: OR of literals2n possible assignments! “DNF”(disjunctive normal form): an OR of ANDsTheorem: ( Cooks Theorem, 1971) SAT(satisfiability) is of (i) SAT NP Why ? (ii) NP , SAT How ? Well, .LSAT = L(SAT,e) L NP , L LSAT There are infinitely many problems in NP !How to get around this pro

40、blem ?Direct proof of Cooks Theorem NP, SAT. How ?An NDTM programM accepting ,i.e., x (in polynomial time)Describe Ms moves using the generic instance of SAT !Why ? NP an NDTM program M accepting in p(n) time,i.e., LM = L( , e) SATLM=L(,e) NPL(,e) fL : * 1* L(,e) * L(SAT,e1) 1* x * , x L(,e) fL(x) L

41、(SAT,e1)Let L(,e) = LM for some NDTM M. Since M = (Q, , , , q0 ,b,F), fL will be derivedin terms of P, Q, , , , q0 , qN , qY, !Basic ideaU and C are constructed so that an NDTM program M accepts x in *iff fL(x) has a satisfying truth assignment.- U and C is a generic instance of SAT.- fL (x) ?How ?S

42、uppose that x * is accepted by M.There is an accepting computation for M on x such that (i) The number of steps in the checking stage is bounded by P(n) , n = |x|. (ii) The number of steps in the guessing stage is bounded by P(n) , n = |x|. (ii) implies that the number of symbols in the guessing str

43、ing is boundedby P(n), n = |x|Only the tape squares within this range can be involved in the computationGSFSCbbb.-2-1012-P(n)P(n)qiThe status of checking computation at any one time can be specified completely by giving(i) The content of tape squares(ii) The current state(iii) The position of W/R he

44、adThere are at most P(n) + 1 times to be considered !Why ? Such a computation can be described completely using only (i) a limited number of Boolean variables (ii) a truth assignment to themIDq0 , q1 = qN , q2 = qY , q3, . , qr r = | Q | - 1s0 = b , s1 , s2 , s3 , . , sv v = | - 1Qi,k 0i p(n) At tim

45、e i (upon completion of 0k r the ith step),M is in state qk.Hi,j 0i p(n) At time i,the read-write head is -p(n)j p(n)+1 scanning tape square j.Si,j,k 0i p(n) At time i, the contents of tape -p(n)j p(n)+1 square j is symbol sk. 0k v Variable Range Intended meaning|Q|=r+1|U| = O(P(n)2)What if the prog

46、ram M halts before time P(n) ? -1 0 1 2 n. . . . .xnoteInitially there is an accepting computation of M on x there is an accepting computation of M on x with p(n)or fewer steps in its checking stage and with a guessedstring w of length exactly p(n) there is a satisfying truth assignment for the coll

47、ectionof clauses in fL(x).Now , using previous Boolean variables construct clauses for fL(x). Restricting the behavior of the polynomial NDTM program M !x LM Qi,0 , Qi,1, . . . , Qi,r , 0i p(n) Qi,j , Qi,j , 0i p(n), 0 j j rat leastone stateno more than one state|Q| = r + 1(P(n)+1)(r+1)(r/2)(P(n)+1) rG1 At each time i, M is in exactl