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

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

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

It then follows by induction that thehorizontal edge markings between the nth and the n + 1st rows will spell theconfiguration right after the nth step of some legal computation of M on inputx. Since no computation of M on input x continues for more than p(lxl) = s - 2steps, the upper markings of the s - 2nd row must contain one of the symbolsy and n. Since there is an s - 1st row, and there is no tile with lower markingn, we must conclude that the symbol y appears, and thus the computation isaccepting. We conclude that if a tiling of the s x s square with V exists, thenM accepts x.Conversely, if an accepting computation of M on input x exists, it can beeasily simulated by a tiling (possibly by repeating the last row several times, ifthe computation terminates in fewer than p(lxl) steps at state y).

The proof iscomplete .•We can now use BOUNDED TILING to prove the main result of this section:Theorem 7.2.2 (Cook's Theorem): SATISFIABILITY is NP-complete.Proof: We have already argued that the problem is in NP; we shall next reduceBOUNDED TILING to SATISFIABILITY.Given any instance of the BOUNDED TILING problem, say the tiling systemV = (D,H,V), side s, and bottom row fa, where D = {d1, ... ,dk}, we shallshow how to construct a Boolean formula T(V, s, fa) such that there is an s x stiling f by V if and only if T(V, s) is satisfiable.The Boolean variables in T(V, s, fa) are Xmnd for each 0 ~ m, n < .9 andd E D.

The intended correspondence between these variables and the tilingproblem is that variable Xmnd is T if and only if f(m, n) = d. We shall nextdescribe clauses which guarantee that f is indeed a legal s x s tiling by V.We first have, for each m, n < s, the clause(Xmnd 1V :E mn d2 V ... V Xmnd k V),7.2: Cook's Theorem313st.at.ing that each posit.ion has at least. one tile. For each m, n < s and eacht.wo distinct. tiles d::j:. dt E D, we have t.he clause (Xmnd V Xmnd'), stating t.hat aposition cannot have more than one tile. The clauses described so far guaranteethat the Xmnd'S represent a function f from {O, ... , s - I} x {O, ...

, s - I} to D.We must next construct clauses stating that the function described by theXmnd'S is a legal tiling by V. We first have clauses (XiO!o(i)) for i = 0, ... , s - 1,forcing f(i, 0) to be fo(i). Then, for each n < sand m < s - 1, and for each(d, dt ) E D2 - H, we have the clause(XmndV Xm+l,n,d'),which forbids two tiles that are not horizontally compatible to be horizontallynext to each other. For vertical compatibility, we have for each n < s - 1 andm < 8, and for each (d, dt ) E D2 - V, the clause (Xmnd V Xm,n+l,d').

Thiscompletes the construction of the clauses in T(V, s). It. remains to show thatT(V, s, fa) is satisfiable if and only if there is an s x s tiling by V that extendsfa.Suppose then that T(V, s, fa) is satisfiable, say by the truth assignment T.Since the big disjunctions are satisfied by T, for each m and n there is at. leastone d E D such that.

T(Xmnd) = T. Since the clauses (Xmnd V Xmnd') are allsatisfied by T, there is no m and n such that two or more Xmnd'S are T underT. Hence T represents a function f : {O, ... , s - I} x {O, ... , s -I} I--t D.We claim that f (m, n) is a legal s x s tiling that extends fa. First, sincethe clauses (XiO!o(i)) are all satisfied, it must be the case that f(i,O) = fo(i),as required.

Then the horizontal adjacency constraint must be satisfied, because, if it is not sat.isfied at positions (m, n) and (m + 1, n), then one of theclauses (Xmnd V Xm+l,n,d') is left unsat.isfied. Similarly for vertical adjacency;thus f (m, n) is indeed a legitimate s x s tiling extending fa.Conversely, suppose that an s x s tiling f extending fa exists. Then definethe following truth assignment T: T(Xmnd) = T if and only if f(m, n) = d.

It iseasy to check that T satisfies all clauses, and the proof is complete .•Thus there is no polynomial-time algorithm for SATISF'IABILITY, unless P =As we have seen in Section 6.3, the special case of 2-SATISFIAB[LITYcan be solved in polynomial time. The following theorem suggests that theimmediately next most involved case is already intractable. In analogy with2-SATISFIABILITY, let 3-SATISFIABILITY be the special case of SATISFIAB[LITYin which all clauses happen to involve three or fewer literals.NP.Theorem 7.2.3: 3-SATISFIABILITY is NP-complete.NP, as it is the special case of a problem in NP.To show completeness we shall reduce SATISFIABILITY to 3-SATISFIABILITY.This is a rather common kind of reduction, in which a problem is reduced toProof: It is of course in314Chapter 7: NP-COMPLETENESSits own special case. Such reductions work by showing how, starting from anyinstance of the general problem, we can get rid of the features that prevent thisinstance from falling within the special case.

In the present situation we mustshow how, starting from any set of clauses F, we can arrive in polynomial timeat an equivalent set of clauses T(F) with at most three literals in each clause.The reduction is simple. For each clause in F with k > 3 literals, saywe do the following: We let Yl, ... , Yk-3 be new Boolean variables, appearingnowhere else in the Boolean formula T(F), and we replace clause C with thefollowing set of clauses:We break up all "long" clauses of F this way, using a different set of Yi variablesin each. We leave "short" clauses as they are. The resulting Boolean formula isT(F).

It is easy to see that T can be carried out in polynomial time.We claim that T(F) is satisfiable if and only if F was satisfiable. Theintuition is this: Interpret the variable Yi as saying, "at least one of the literalsAi+2' ... ,Ak is true," and the clause (Yi V Ai+2 V Yi+d as saying, "if Yi is true,then either Ai+2 is true, or Yi+l is true."formally, suppose that truth assignment T satisfies T(F).

We shall showthat T also satisfies each clause of F. This is trivial for the short clauses; and ifT maps all k literals of a long original clause to .1, then the Yi variables wouldnot be able by themselves to satisfy all resulting clauses: The first clause wouldforce Yl to be T, the second Y2 to be T, and finally the next-to-last clause wouldcause Yk-3 to be T, contradicting the last clause (incidentally, notice that thisis precisely the purge algorithm solving this instance of 2-SATISFIABILITY).Conversely, if there is a truth assignment T that satisfies F, then T canbe extended to a truth assignment that satisfies T(F), as follows: For each longclause C = (AI V A2 V ...

V Ak) of F, let j be the smallest index for whichT (Aj) = T (since T was assumed to satisfy F, such a j exists). Then we set thetruth values of the new variables Yl, ... , Yk-3 to be T' (Yi) = T if i ~ j - 2, andto be T'(Yi) = .1 otherwise. It is easy to see that T now satisfies T(F), and theproof of equivalence is complete. •Consider finally the following optimization version of SATISFIABILITY:MAX SAT: Given a set F of clauses, and an integer K, is there a truthassignment that satisfies at least K of the clauses?3157.2: Cook's TheoremTheorem 7.2.4: MAX SAT is NP-complete.Proof: Membership in NP is obvious. We shall reduce SATISFIABILITY to MAXSAT.This reduction is an extremely simple one, but of a kind that is very common and very useful in establishing NP-completeness results (see Problem 7.3.4for many more examples). We just have to observe that MAX SAT is a generalization of SATISFIABILITY; that is, every instance of SATISFIABILITY is a specialkind of instance of MAX SAT.

And this is true: An instance of SATISFIABILITYcan be thought of as an instance of MAX SAT in which the parameter f{ happensto be equal to the number of clauses.Formally, the reduction is this: Given an instance F of SATISFIABILITYwith m clauses, we construct an equivalent instance (F, m) of MAX SAT by justapending to F the easily calculated parameter K = m. Obviously, there is atruth assignment satisfying at least K = m clauses of F (of which there areexactly m) if and only if there is one that satisfies all clauses of F .•As it turns out, the restriction of MAX SAT to clauses with at most twoliterals can be shown to be also NP-complete (compare with 2-SATISFIABILITY).Problems for Section 7.2.2.1.

Let us consider what happens in the reduction from L to BOUNDED TILINGwhen L is in P -that is to say, when the machine M in the proof ofTheorem 7.2.1 is actually deterministic. It turns out that, in this case, theresulting tiling system can be expressed as a closure of a set under certainrelations.Let Al be a deterministic Turing machine deciding language L in timep(n), a polynomial; let x be an input of M; and let s, (D, H, V), andfa be the components of the bounded tiling instance resulting from thereduction in the proof of Theorem 7.2.1 applied to x.

Consider the setsp = {O, 1, 2, ... , s - I} and 5 = P x P x D. Let 50 ~ 5 be the followingset:{(m,O,fo(m)): ~ m < s}.°Let RH~5 x 5 be the following relation:R{((m -1,n,d),(m,n,d')): 1 ~ m,nand Rv~< s, (d,d')E H},5 x 5 be this:R{((m,n -I,d), (m,n,d')):°~'In< s, 2 ~ n < s, (d,d')E V}.316Chapter 7: NP-COMPLETENESSShow that x E L if and only if the closure of So under RH and Rv contains,for each 0 :; i, j < s, a triple (i, j, d) for some d ED. In other words, notonly can any closure property can be computed in polynomial time (thiswas shown near the end of Section 1.6), but also, conversely, any polynomialcomputation can be expressed as a closure property. Of course, the use ofhuge relations such as RH makes this result seem a little artificial; but itturns out that it also holds in a much more meaningful setting (see thereferences at the end of the chapter).7.2.2.

Consider BINARY BOUNDED TILING, the version of BOUNDED TILING wherewe are not given the first row of tiles, but only the tile at the origin, do; thesize of the square to be tiled, 8, is given in binary.(a) Show that there is a reduction from the languageEI = {"M": M halts on the empty string within 2 I" M "I steps}to BIi'.'ARY BOUi'.'DED TILmG.(b) Conclude that BINARY BOUNDED TILING is not in P.(c) Let NEXP be the class of all languages decided by a nondeterministicTuring machine in time 2nk for some k > O.

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

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