1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 62
Текст из файла (страница 62)
In any event, after O(n) steps of this sort,where n is the number of clauses in the given formula, the purge must indeedeither fail (in which case we decide that the formula is unsatisfiable), or haltwith a set of clauses each of which has two distinct literals. In (2), for example,the initial purge ends up setting T(xt) = T, T(X2) = ..1, and deleting the firstfour clauses.We can therefore assume that we have a formula with precisely two literalsin each clause. How can we look for a satisfying truth assignment? Here is asimple idea: Take any variable whose truth value has not been assigned yet, trysetting its truth value to T, and perform the purge; then restore the formula inits original form, set the same variable to ..1 and perform the purge again.
Ifboth purges fail, we give up; the formula is unsatisfiable. If however at least oneof the two purges succeeds, then we set the variable to the successful truth valueand continue. In our example trying the value T(X3) = T in the four clausesthat remain after the first purge,(3)starts a new purge that fails after setting T(X5) = T (the clauses (X4) and (X4)result); so we must restore the four clauses in (3) and try T(X3) =..l. Thissucceeds in finding a satisfying truth assignment for the whole formula (thereare no clauses left), namely T(X4) = T and T(X5) = ..l.It is easy to see (Problem 6.3.2) that this simple algorithm correctly solvesthe satisfiability problem when there are at most two literals per clause.
Sincethe algorithm performs at most two purges for each variable, and each purgecan be performed in polynomial time, it follows that 2-SATISFIABILITY is in P.Problems for Section 6.36.3.1. Find all satisfying truth assignments of the Boolr~an formula consisting ofthese clauses: (:1:1 V X2 V X3), (Xl V X4), (X2 V X3 V X4).Chapter 6: COMPUTATIONAL COMPLEXITY2926.3.2.
(a) Show that the purge algorithm described in the text correctly solves anyinstance of 2-SATISFIABILITY in polynomial time. (Hint: Suppose the purgealgorithm decides the formula is unsatisfiable, and yet a satisfying truthassignment exists.
How did the purge algorithm miss this assignment?)(b) What is the lowest polynomial bound you can show for this algorithm?(c) How would the purge algorithm work on this formula? (Xl V X2), (Xl VX4), (X2 V X3)(XI V X4), (X3 V X4).6.3.3. This is an alternative proof that 2-SATISFIABILITY is in P. Any clause withtwo literals, say (x V y), can be thought of as two implications, namely(x -+ y) and Cfi -+ x) (the clause (x) can be thought of as (x -+ x)). Thus,starting from any instance of 2-SATISFIABILITY, we can construct a directedgraph with all literals as nodes that depicts all these implications.
Showthat an instance of 2-SATISFIABILITY is un satisfiable if and only if there isa variable x such that there is a path from x to x and a path from x to xin this graph. Conclude that 2-SATISFIABILITY is in P.BTHE CLASS NPOne of the main goals of complexity theory is to discover mathematical methodsthat will help us prove that problems of interest are not in P. We have alreadyseen such a method: The diagonalization argument used to establish, in fullanalogy with the unsolvability of the halting problem H, that E ~ P, where Eis the languageE = {"M" "w" : M accepts input w after at most 21wl steps}(Theorem 6.1.2).
However, this result is hardly satisfying. The reason is that,unlike the notion of decidability, P and polynomial-time computation are concepts of earthy, practical motivation. It is not enough to exhibit an artificialhalting-like problem like E and argue that it is not in P. We want to identifynatural, reasonable, practically important problems that are not in P.We saw in the last section a plethora of natural, reasonable problems, quiteplausibly of practical interest, that appear not to belong in P: HAMILTON CyCLE, the TRAVELING SALESMAN PROBLEM, INDEPENDENT SET, PARTITION,SATISFIABILITY.
Despite prolonged, intense efforts by mathematicians and computer scientists to discover a polynomial-time algorithm for each of these problems, none has been found. It would be most worthwhile, then, to use the ideasand methods of computational complexity to establish that no such polynomialtime algorithm is possible, thus saving our fellow scientists from further ill-fatedattempts.6.4: The Class NP293Unfortunately, there is a subtle difficulty in coming up with such an impossibility proof. The reason is that, as we shall see next, all of these problems canbe solved by polynomially bounded nondeterministic Turing machines. And separating determinism from nondeterminism at the polynomial-time level is oneof the most important and deep unsolved problems in computer science today.It was established in Chapter 4 that if a language L is decidable in polynomial time by a Turing machine of one of several varieties (single-tape, multipletape, two-dimensional, even random access), then L is decidable in polynomialtime by a machine of any of the other kinds.
What about the last variant ofthe Turing machine model that we have introduced in Chapter 4, namely thenondeterministic Turing machine (Section 4.6)? Is it also equivalent to the remaining kinds, up to a polynomial? In order to discuss this important issue, letus first define formally what we mean by saying that a language is decided by anondeterministic Turing machine within a polynomial time bound; the definitionis a straightforward extension of that for deterministic machines.Definition 6.4.1: A nondeterministic Turing machine M = (K, '5:., 1:1, H) issaid to be polynomially bounded if there is a polynomial p(n) such that forany input x, there is no configuration C of M with (s, C>1Jx) f--~IXIl+l C; thatis, no computation of this machine continues for more than polynomially manysteps. And define NP (for nondeterministic polynomial) to be the classof all languages that are decided by a polynomially bounded nondeterministicTuring machine.It is important at this point to recall the peculiar definition of what it meansfor a nondeterministic machine to decide a language L: For each input not inL, all computations of the machine must reject the input; for each input in L,we only require that there be at least one computation that accepts the input-none, some, most, or all of the other computations may reject the input, aslong as there is at least one accepting one.The set of all possible computations of a nondeterministic Turing machineon a given input is best pictured by a treelike structure (see Figure 6-3).
Nodesrepresent configurations, and downward lines are steps. Nondeterministic choicesare represented by nodes that have more than one downward line leaving them.Time is measured in the vertical dimension. In Figure 6-3, for example, theinput is accepted after five steps.Such a picture makes it transparent why nondeterminism is such a powerfulmode of computation: There are astronomically many configurations that areproduced in very short time (vertical distance from the root).
As we shall see inthe next examples, this power of nondeterminism can be put to use in "solving"some of the formidable problems we have seen in the last section.Example 6.4.1: We mentioned in the previous section that it is widely believedChapter 6: COMPUTATIONAL COMPLEXITY294nn nnnn nnynnnnnnyn nn nnnnFigure 6-3that SATISFIABILITY is not in P. Let us now show that it is in Np. We shalldesign a nondeterministic TUring machine M that decides in polynomial nondeterministic time all encodings of satisfiable Boolean formulae in conjunctivenormal form.M operates as follows: On input w, it first checks to see whether w is indeedthe encoding of a Boolean formula in conjunctive normal form (if not, it rejectsimmediately), and counts the number of variables, n, that appear in it.
This iseasy to accomplish deterministically in polynomial time. At the end of this firststage, the second tape of M contains the string r>Jn, with as many J's as theformula has variables.Then M goes into a nondeterministic phase, during which it writes onits second tape a sequence of n T's and ..l's over the 1's. Which sequenceof T's and ..l's, exactly? The answer is "any sequence, nondeterministically."A more precise answer is perhaps "all sequences, each in a different branchof the tree of nondeterministic computations." It is easy to design a nondeterministic machine that does this: Just add a new state q to K, and addto ~ the transitions (ignoring the other tapes, where no activity takes place)(q,I,q, T), (q,J,q,..l), (q, T,q,-+),(q,..l,q,-+),(q,U,q',U), where q' is the statethat continues the computation.The final phase of M is deterministic: M interprets the string in {T, ..l } n inits second tape as a truth assignment for the input formula.
It then visits eachclause of the input one by one, and checks whether it contains a literal that is6.4: The Class NP295T under the truth assignment. If it finds that all clauses have a T literal, Maccepts. Otherwise, if an unsatisfied clause is found, M rejects.It is straightforward to see that M, as described above, establishes thatSATISFIABILITY is in NP. First, all computations are of length bounded bysome small polynomial. For the crucial part, if the input encodes a satisfiableBoolean formula, then M will "guess" the satisfying truth assignment at somebranch of the nondeterministic computation, and will therefore have at least oneaccepting computation -in addition to possibly many rejecting ones.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
