1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 63
Текст из файла (страница 63)
Hence theinput will be accepted. If the input formula is unsatisfiable, or not a formula atall, then all computations will end up rejecting. <)Example 6.4.2: The TRAVELING SALESMAN PROBLEM (as defined in Section6.2 with the "budget" B given) is also in Np. The nondeterministic Turingmachine that achieves this writes in its second tape, nondeterministically, astring of zeros, ones, and u's of length equal to that of the input. Then themachine enters a deterministic phase, in which it checks to see if the stringwritten on its second tape happens to be the encoding of a bijection 7r of theintegers 1, ...
, n where n is the number of cities in the given input -bijection7r is encoded by writing 7r(1), 7r(2), ... in binary, separated by U's. If the stringis indeed the encoding of a bijection, the machine goes on to deterministicallycalculate the cost of the tour, and compare it with the "budget" B in its input. Ifthe cost is smaller, the machine accepts; in all other eventualities (if the guessedstring is not the encoding of a bijection, or if it represents a tour with cost greaterthan B) the machine rejects.
It is clear that a string is in the language decidedby this machine if and only if it encodes a "yes" instance of the TRAVELINGSALESMAN PROBLEM.Similarly, it is easy to show that the other apparently difficult problemswe encountered in the previous section, INDEPENDENT SET, HAMILTON CYCLE,and PARTITION (though not EQUIVALENCE OF NONDETERMINISTIC FINITE AUTOMATA) are also in NP.<)Notice how cleverly the nondeterministic "algorithms" of the two previousexamples exploit the fundamental asymmetry in the definition of nondeterministic time-bounded computation.
They tryout all possible solutions to the problem in hand in independent computations, and accept as soon as they discoverone that works -oblivious of the others that do not.The analogy with the class of recursively enumerable languages, anotherclass whose definition had an asymmetry of a similar kind between acceptanceand rejection, is tempting here. As with that class, it is not at all clear that Npis closed under complement (while it is clear in the case of P, as well as the classof recursive functions). Also, it is immediate that P ~ NP (the analog of thefact that every recursive language is recursively enumerable).
This is because296Chapter 6: COMPUTATIONAL COMPLEXITYdeterministic machines are simply nondeterministic ones in which the transitionrelation happens to be a function.Is P equal to NP? In other words, are nondeterministic Turing machinesyet another version of Turing machines equivalent to the rest with respect to theclass of languages decided in polynomial time? At first glance, one gets the intuitive feeling that nondeterminism is such a strong and "different" feature thatthis should not be the case. The trees that represent the set of computationsof a nondeterministic Turing machine (recall Figure 6-3) have many nodes (thatis, configurations), all at a moderate depth. The only way that a deterministicTuring machine can compete with the nondeterministic one with respect to thenumber of reachable configurations is by operating for an exponential numberof steps.
The nondeterministic machines that decide SATISFIABILITY and theTRAVELING SALESMAN PROBLEM above search quite effortlessly an exponentially large population of possibilities; it would be truly remarkable if the sameeffect could be achieved in a methodical deterministic manner in polynomialtime.This difficulty of using a deterministic Turing machine to search a large set of"solutions" was also reflected in the proof of Theorem 4.5.1.
It was shown therethat a nondeterministic Turing machine can be simulated by a deterministicone; but that simulation was not a direct step-by-step simulation, like the onesof Theorems 4.3.1 and 4.3.2 (for which we were able to prove polynomial bounds).The simulation of a nondeterministic Turing machine resorted to an exhaustiveexamination of all possible computations. Again, one gets the intuitive feelingthat this is inherent in nondeterminism, since it allows multiple choices at eachstep, and so there is an exponentially large multitude of possible computationsto be checked.In order to compare nondeterministic and deterministic machines in termsof their time performance, we must first define a much more general class oflanguages:Definition 6.4.2: A Turing machine M = (K,~, S, s, H) is said to be exponentially bounded if there is a polynomial p(n) such that the following istrue: For any input x, there is no configuration C such that (s, C>!Jx) f-;;(1'1)+1 C.That is, the machine always halts after at most exponentially many steps.Finally, define E XP to be the class of all languages that are decided bysome exponentially bounded Turing machine.Theorem 6.4.1: If L ENp, then LEEXP.Proof: Suppose that we are given a nondeterministic polynomially boundedTuring machine M deciding L with time bound p(n).
We shall show how to2976.4: The Class NPconstruct a deterministic Turing machine M' that decides the same languagein time cp(n) for some constant c (the theorem then follows, by considering thepolynomial k· p(n), for some k such that 2k > c).
M' is precisely the machineconstructed in the proof of Theorem 4.5.1. M' simulates M on all possiblecomputations of length 1, then on all possible computations of length 2, andso on, up to length p(n) + 1, at which point either an accepting computationhas been discovered, or all computations have halted rejecting. To simulatea computation of M of length £, M' needs 0(£) steps -to copy the input, toproduce the next string in {I, 2, ... , r}C (where r is the degree of nondeterminismof M, a fixed number depending only on M and equal to the maximum possiblenumber of quadruples in ~ that share the same first two components), and tosimulate M following the choices suggested by this string.
Thus, M' can carryout the simulation of M on an input of length n in timep(n)+1LrC:S (r+ 1)p(n)+1,{=1which completes the proof with c= r + 2.•As we have already mentioned, whether P = NP is a question of centralimportance to complexity theory that is presently unresolved. Whether NP =EXP, that is, whether the inclusion in the above corollary is proper, is anotherquestion which, although quite a bit less important, is equally open. We doknow the following, however: In the chain of inclusionsP ~ NP ~ EXP,the third class properly -includes the first.
The reason is that the language E,shown in Theorem 6.1.2 not to be in P, is certainly in EXP: A Turing machinecan in exponential time simulate M on input w for 21wl steps. Thus, although wesuspect that both of the inclusions displayed above are proper, all we can currentlyprove is that at least one of them is proper -and we do not know which . ..Succinct CertificatesThe nondeterministic Turing machines we devised in Examples 6.4.1-2 for deciding SATISFIABILITY and the TRAVELING SALESivIAN PROBLEM are quite simple,and somewhat similar: They start by nondeterministically generating a string,and then check deterministically whether the generated string has a certain required property in relation to the input.
If the input is in the language, then atleast one appropriate string exists. If the input is not in the language, then nostring with the required property can be found.Such a string is called a certificate, or a witness. As we shall see, allproblems in NP have certificates, and only problems in NP do. A certificate298Chapter 6: COMPUTATIONAL COMPLEXITYmust be polynomially succinct, that is, of length that is at most a polynomialin the length of the input.
It must also be checkable in polynomial time. In thecase of SATISFIABILITY, checking the certificate entails testing whether the truthassignment satisfies all clauses of the input formula; in the case of the TRAVELINGSALESMAN PROBLEM, testing whether the proposed tour has a total cost withinthe budget; for INDEPENDENT SET, whether the given set of nodes is of the rightsize and free of edges; and so on. Finally, all "yes" inputs of a problem musthave at least one certificate, while all "no" inputs mllst have none.The idea of certificates can be formalized in the domain of languages, providing an interesting alternative definition of NP.Definition 6.4.3: Let L be an alphabet, and let ";" be a symbol not in L.Consider a language L' 5;; L*; L*. We say that L' is polynomially balancedif there exists a polynomial p(n) such that if x; y E L', then Iyl ::; p(lxl).Theorem 6.4.2: Let L 5;; L* be a language, where i rf- L, and ILl 2' 2.
ThenL E NP if and only if there is a polynomially balanced language L' 5;; L*; L*such that L' E P, and L = {x : there is ayE L* such that x; y E L' }.Proof: Intuitively, language L' summarizes all certificates of all inputs. Thatis,L = {x; y: y is a certificate for x}.For each x E L*, there is a set of y's such that Xi y E L'; this set is the set ofcertificates of x. If x is in L, then its set of certificates has at least one element;if x rf- L, then this set of certificates is empty.If such a language L' exists, then a nondeterministic Turing machine coulddecide L by trying all certificates (very much like the nondeterministic Turingmachine that decides SATISFIABILITY does) and then utilizing the deterministic1\lring machine that decides L'. And conversely, any nondeterministic Turingmachine M deciding L provides a solid framework for certificates for L: Acertificate for an input x is precisely any accepting computation of AI on inputx -both concise and polynomially checkable.The formal proof is left as an exercise (Problem 6.4.5) .•This concept of succinct certificates is best illustrated in terms of the setC 5;; N of composite numbers (recall the discussion in Example 4.5.1).
Supposethat we are given a natural number in its usual decimal representation -forinstance, 4,294,967,297 -and asked whether it is composite. There is no clear,efficient way of answering such questions. However, every number in C does havea succinct certificate. For example, the number 4,294,967,297, which happensto be composite, has as a certificate the pair of integers 6,700,417 and 641 that299Referenceshave a product of 4,294,967,297. To check the validity of the certificate, one justhas to carry out the multiplication to be convinced that 4, 294, 967,297 E C. Andthis is the !-iubtlety of a certificate: Once you have found it, you can efficientlyexhibit its validity. But finding it may not be easy: The above factorization of4,294,967,297 was first discovered by the mathematician Leonard Euler (17071783) in 1732, a full 92 years after Pierre de Fermat (1601-1665), another greatmathematician, had conjectured that no such factorization existed!Problems for Section 6.46.4.1.
Show that NP is closed under union, intersection, concatenation, andKleene star. (The proofs for NP are much simpler that those for P.)fE :6.4.2. Define coNP to be the following class of languagesL E NP}. It isan important open problem whether NP =coNP, that is, whether NP isclosed under complement.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
