1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 66

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 66)

Then P = NP if andonly if L E P.Proof: (Only If) Suppose that P = NP. Since L is NP-complete, and henceL E NP (recall that an NP-complete language must be in NP), it follows thatLEP.(If) Suppose that L is an NP-complete language that is decided by a deterministic Turing machine MI in time PI (n), a polynomial, and let L' be any languagein NP; we shall show that L' E P.Since L is NP-complete and L' E Np, then there is a polynomial reductionT from L' to L (we are now using the second part of the definition of an NPcomplete language).

Suppose that T is computed by some Turing machine M2in time P2(n), also a polynomial. Then we claim that the Turing machine M2MIdecides L' in polynomial time. To see that M2MI decides L', notice that M2MIaccepts input x if and only if T(X) E L; and since T is a polynomial reduction,T(X) E L if and only if x E L'.Finally, to analyze the time requirements of M2 M I , notice that its initialM2 part takes, on input x, time P2(lxl) to produce an input for MI. Thisinput will have length at most P2(lxl), because M2 cannot write more than onesymbol per step. Hence, the computation of MI on this input will take timeat most PI (P2(1XI)).

The overall machine will halt, on input x, within timeP2(lxl) + PI(P2(lxl) + Ixl), and this is a polynomial in Ixl·Since L' was taken to be any language in NP and we concluded that L' E P,it follows that NP = P .•Problems for Section 7.17.1.1. In 3-COLORING we are given an undirected graph, and we are asked whetherits nodes can be colored with three colors such that no two adjacent nodeshave the same color.(a) Show that 3-COLORING is in NP.(b) Describe a polynomial-time reduction from 3-COLORING to SATISFIABILITY.7.2: Cook's Theorem3097.1.2. Some authors define a more general notion of reduction, often called polynomial Turing reduction.

Let Ll and L2 be languages. A polynomialTuring reduction from Ll to L2 is a 2-tape Turing machine with threedistinguished states, q?, ql, and qo, that decides L2 in polynomial time,and whose computation is defined in a rather peculiar way. The yieldsrelation of M for all configurations with states other than q? is definedexactly as for ordinary Turing machines. For q?, however, we say that(q?,I>Ul~hVl,I>U2Q2V2) I-M (q,I>U~Q~v~,I>U~Q~v~) if and only if(1) Ul = u~, a~ = aI, v~ = VI, U2 = U~, a~ = a2, v~ = V2, and(2) one of the following holds: either(2a) U2a2V2 E Ll and ql = ql, or(2b) U2a2v2 ~ Ll and ql = qo.In other words, from state q?, M never changes anything on its tapes; itjust goes to state ql or qo, depending on whether or not the string in itssecond tape is in L l . Furthermore, this counts as one step of M.(a) Show that if there is a polynomial Turing reduction from Ll to L 2, andone from L2 to L 3, then there is a polynomial Turing reduction fromLl to L 3.(b) Show that if there is a polynomial Turing reduction from Ll to L 2 , andL2 E P, then Ll E P.(c) Give a polynomial Turing reduction from HAMILTON CYCLE to HAMILTON PATH (the version in which we are not requiring that the paththat visits each node exactly once is closed).

Can you find a direct(that is, not using the reduction in the proof of Theorem 7.3.2 below)polynomial reduction between the two problems?liiJCOOK'S THEOREMWe have not yet established that NP-complete languages exist -but they do.During these past two decades research in computational complexity has discovered literally hundreds of such NP-complete languages (or NP-completeproblems, as we shall continue to blur the distinction between computationalproblems such as SATISFIABILITY and HAMILTON CYCLE and the languages thatencode them). Many of these NP-complete problems are important practicalproblems from operations research, logic, combinatorics, artificial intelligence,and other seemingly unrelated application areas.

Prior to the discovery of Npcompleteness, much research effort had been devoted in vain to finding polynomial algorithms for many of these problems. The concept of NP-completenessunified the experiences of researchers in these diverse areas by showing that noneof these problems is solvable by a polynomial-time algorithm unless P = Np a circumstance that appears to contradict both intuition and experience. ThisChapter 7: NP-COMPLETENESS310realization has had the beneficial effect of diverting the research effort previously focused on solving particular NP-complete problems towards other, moretractable goals, which are the subject of Section 7.4. This redirection of research effort has been the most profound effect of the theory of computation oncomputational practice.Bounded TilingOnce we have proved the first NP-complete problem, more problems can beshown NP-complete by reducing to them a problem already known to be NPcomplete, and using the transitivity of polynomial reductions, recall Lemma7.1.1.

But the first NP-completeness proof must be an application of the definition: We must establish that all problems in NP reduce to the problem in hand.Historically, the first problem to be shown NP-complete by Stephen A. Cookin 1971 was SATISFIABILITY. Instead of giving that proof directly, we shall startwith a version of the tiling problem that was shown to be undecidable in Chapter5.In the original tiling problem we were given a tiling system D, and we wereasked whether there is a way to tile the infinite first quadrant so that any twovertically or horizontally adjacent tiles are related as prescribed, and a given tileis placed at the origin. We can define a less ambitious problem, called BOUNDEDTILINC, in which we are asked whether there is a legal tiling, not of the wholequadrant, but of an 8 x 8 square, where 8 > 0 is a given integer.

This time,instead of specifying only the tile placed at (0,0), we specify the entire first rowof tiles. That is, we are given a tiling system D = (D, H, V) (where we omitthe starting tile do, which is now irrelevant), an integer 8 > 0, and a functionfo : {O, ... , 8 - I} I--t D. We are asked whether there is an 8 x 8 tiling by Dextending fo, that is, a function f : {O,I, ...

, 8 -I} x {O,I, ... , 8 -I} I--t D suchthatf(m,O) = fo(m) for all m < s;(f(m, n), f(m + 1, n)) E H for all m < 8 - I, n < s;(f(m,n),f(m,n + 1)) E V for all Tn < 8,n < 8-l.The BOUNDED TILING problem is this:Given a tiling system D, an integer 8, and a function fo :D, represented by its sequence of values (/0(0), ... , fO(81)), is there an 8 x s tiling by D extending fo?BOUNDED TILING{O, ... , s - I}I--tTheorem 7.2.1: BOUNDED TILING is NP-complete.Proof: Let us first argue that it is in NP.

The certificate in this case is acomplete listing of the S2 values of a tiling function f. Such a function can bechecked in polynomial time for compliance with the three requirements. Furthermore, it is succinct: Its total length is S2 times the number of symbols it7.2: Cook's Theorem311takes to represent a tile, and s is bounded from above by the length of the inputbecause the input includes the listing 01 10. Actually, the purpose of this twistto our tiling formalism was precisely to ensure that the problem is in Np; if weonly specify one starting tile, the problem becomes much harder -it is provablynot in P; see Problem 7.2.2.We must now show that all languages in NP reduce via polynomial reductions to BOUNDED TILING.

SO, consider any language L E Np. We must producea polynomial reduction from L to BOUNDED TILING, that is, a polynomial-timecomputable function T such that for each x E 1:', T(X) is the encoding of a tilingsystem D = (D, H, V), plus an integer s > 0 and the encoding of a function 10,with this property: There is an 8 x 8 tiling with D extending 10 if and only ifx E L.To obtain this reduction, we must somehow exploit the little informationwe have about L. All we know about L is that it is a language in NP; thatis, we know that there is a nondeterministic Turing machine M = (K, 1:, J, s)such that (a) all computations of M on input x halt within p(lxl) steps for somepolynomial p, and (b) there is an accepting computation on input x if and onlyif x E L.We start by describing the integer 8 constructed by T on input x: it iss = p(lxl) + 2, two more than the time bound of M on input x.The tiling system D described in T(X) will be very similar to the one constructed in the proof of the undecidability of the unbounded tiling problem(Theorem 5.6.1).

We shall describe the tiles in D, as in that construction, bytheir edge markings; once more, the markings of the horizontal edges betweenrows t and t + 1 will represent the tape contents of M in a legal computationwith input x right after the tth step (since M is nondeterministic, there maybe several such computations, and therefore there may now be several possiblelegal ways to tile the 8 x 8 square).The Oth row of the s x s square, prescribed by 10, will be occupied by tilesspelling the initial configuration (8,I>UX).

That is, 10(0) is a tile with upper edgemarking 1>, 10(1) is a tile with upper edge marking (s, u), and for i = 1, ... , Ixllo(i + 1) is a tile with upper edge marking Xi, the ith letter of the input x.Finally, for all i > Ixl + 1, lo(i) is a tile with upper edge marking U (see Figure7-3).

Thus, the horizontal edge markings between the Oth and the first rows willspell the initial configuration of M on input x.Figure 7-3The remaining tiles in D are exactly as in the proof of Theorem 5.6.1. Since312Chapter 7: NP-COMPLETENESSthe machine is nondeterministic, there may be more than one tile with bottomhorizontal marking (q, a) E K x ~, corresponding to the possibly many choicesof action when M scans an a in state q, and each of them is constructed asin that proof. There is only one minor difference: There is a tile with bothupper and lower marking (y, a) for each symbol a, effectively allowing the tilingto continue after the computation has halted at state y ~but not if it haltsat state n.

This completes the construction of the instance T(X) of BOUNDEDTILI~G. It should be clear that the construction of the instance can be carriedout in time polynomial in Ixi.We must now show that there is an s x s tiling by V if and only if x EL. Suppose that an s x s tiling exists. Our definition of fa ensures that thehorizontal edge markings between the Oth and the first rows must spell theinitial configuration of M on input x.

Характеристики

Список файлов решённой задачи