1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 64
Текст из файла (страница 64)
Show that if Np ;j:. coNP, then P ;j:. NP.6.4.3. Call a homomorphi!-im h (recall Problems 2.3.11 and 3.5.3) nonerasing ifit map!-i no symbol to e. Show that NP is closed under nonerasing homomorphisms.You may want to think about these question!-i: Is NP closed under generalhomomorphisms? How about the class of recursive languages? How aboutthe recursive enumerable ones? How about P? See Problem 7.2.4 in thenext chapter for the last one.6.4.4. Define appropriate !-iuccinct certificates for PARTITION and CLIQUE.6.4.5. Prove Theorem 6.4.2.REFERENCESThe theory of computational complexity, much anticipated in the late 1950s and early1960s, was formally developed by Hartmanis and Steams in this papero J.
Hartmanis and R. E. Stearns "On the computational complexity of algorithms," Transactions of the American Mathematical Society, 117, pp 285-305,1965;Theorem 6.1.2 follows from results in that paper. The thesis that the class P adequatelycaptures the notion of an "efficiently solvable problem," also implicit in much earlierwork, emerged in the mid 1960s mainly in these two works:o A. Cobham"The intrinsic computational difficulty of functions," Proceedings ofthe 1964 Congress for Logic, Mathematics and the Philosophy of Science, pp.
2430, New York: North Holland, 1964, and300Chapter 6: COMPUTATIONAL COMPLEXITYo J. Edmonds "Paths, trees and flowers," Canadian Journal of Mathematic8, 17,3, pp. 449--467, 1965.In the last paper, the clas8 Np was also informally introduced (in terms of certificates,recall Theorem 6.4.2), and it was first conjectured that P -::j:. Np.
For a much moreextensive treatment of computational complexity, seeo C. H. PapadimitriouWesley, 1994.Computational Complexity, Reading, Massach.: Addison-NP-completeness7.1 POLYNOMIAL-TIME REDUCTIONSMany of the concepts and techniques we use in complexity theory are timebounded analogs of the concepts and techniques that we developed for studyingundecidability. We have already seen in the proof of Theorem 6.1.2 that we canuse the polynomial-time analog of diagonalization in order to show that certainlanguages are not in P.
We shall next introduce polynomial-time reductions, theanalog of the reductions we employed for establishing undecidability in Chapter5. We shall use polynomial-time reductions to study the complexity of severalimportant and seemingly difficult problems in NP introduced in the previouschapter: SATISFIABILITY, the TRAVELING SALESMAN PROBLEM, INDEPENDENTSET, PARTITION, and others. As we shall see, these problems have the followingimportant completeness property: All problems in NP can be reduced to themvia polynomial-time reductions -in much the same way that all recursivelyenumerable languages reduce to the halting problem.
We call such problemsNP-complete.Unfortunately, the analogy with the halting problem breaks down after thispoint. There seems to be no simple diagonalization argument which establishesthat these NP-complete problems are not in P; diagonalization arguments appear to apply only to languages that are too hard and unnatural to matter, suchas the exponential-time language E in Theorem 6.1.2.Despite the fact that these NP-complete problems fail to provide a proofthat P ;j:. NP, they do occupy an important place in our study of complexity: Ifwe assume that P ;j:. NP -a conjecture that is very widely accepted, althoughstill far from proved- then all NP-complete problems are indeed not in P (thisis articulated in Theorem 7.1.1 below).
This somewhat indirect evidence ofdifficulty is the most we can expect for a problem in NP, short of proving that301302Chapter 7: NP-COMPLETENESSP i-NP.But we must now define the polynomial-time variant of reduction (comparewith Definition 5.4.1):Definition 7.1.1: A function f : I;* H I;* is said to be polynomial-timecomputable if there is a polynomially bounded Turing machine !vI that computes it.Let now L 1, L2 <:;;: I;* be languages. A polynomial-time computable functionT : I;* H I;* is called a polynomial reduction from L1 to L2 if for eachx E I;* the following holds: x E L1 if and only if T(X) E L"2'Polynomial reductions are important because they reveal interesting relationships between computational problems. Strictly speaking, a polynomialreduction as defined above relates two languages, not two problems.
However,we know from the discussion in Section 6.2 that languages can be used to encode all kinds of important computational problems, such as HAMILTON CYCLE.SATISFIABILITY, and INDEPENDENT SET. In this sense we can say that T is apolynomial reduction from Problem A to Problem B if it is a polynomialreduction between the corresponding languages. That is, T transforms in polynomial time instances of Problem A to instances of Problem B in such a waythat x is a "yes" instance of Problem A if and only if T(X) is a "yes" instance ofProblem B.r-----------~lgorithmInstanceof Afor A"yes"Algorithmfor BofB~~no"Figure 7-1When we have a polynomial reduction T from Problem A to Problem B, itis possible to adapt any polynomial-time algorithm for B to obtain one for A(see Figure 7-1).
To tell whether any given instance x of Problem A is actuallya "yes" instance of A, one can start by computing T(X), and testing whether ornot it is a "yes" instance of B. If we have a polynomial algorithm for B, thismethod for solving A is also polynomial, since both the reduction step and thealgorithm for solving the resulting instance of B can be done in polynomial time.In other words, the existence of a polynomial reduction from A to B is evidence3037.1: Polynomial-time Reductionsthat B is at least as hard as A.
If B is efficiently solvable, then so must be A;and, if A requires exponential time, then so does B.We give several examples of reductions below.Example 7.1.1: Let us describe a polynomial reduction from HAMILTON CYCLEto SATISFIABILITY. Suppose that we are given an instance of HAMILTON CYCLE,that is, a graph G ~ V x V, where V = {I, 2, ... , n}. We shall describe analgorithm T that produces a Boolean formula in conjunctive normal form T( G),such that G has a Hamilton cycle (a closed path visiting each node of G exactlyonce) if and only if T( G) is satisfiable.Formula T(G) will involve n Z Boolean variables, which we shall denote Xij,with 1 ::; i, j ::; n. Intuitively, Xij will be a Boolean variable with this intendedmeaning: "Node i of G is the jth node in the Hamilton cycle of G." Thevarious clauses of T( G) will then express in the language of Boolean logic therequirements that a Hamilton cycle must satisfy.What requirements must the Xii'S satisfy so that they indeed define a Hamilton cycle of G? We shall cast each such requirement as a clause.
First, forj = 1, ... , n we have the clause(XljV XZj V ... V Xnj).For a truth assignment to satisfy this clause, it must set at least one of thevariables Xlj, XZj, ... ,Xnj to T; thus this clause expresses, under the "intendedmeanings" of the Boolean variables, the requirement that at least one nodeshould appear ith in the Hamilton cycle.But of course, only one node of G can appear ith in the Hamilton cycle.Thus, we add to our Boolean formula all O(n 3 ) clauses of the form(XijVXik)for i, j, k = I, ... ,n and j i- k. Since at least one literal in this clause must besatisfied, these clauses successfully express the requirement that not both nodej and node k can appear ith on the cycle.The clauses so far guarantee that exactly one node appears ith in the Hamilton cycle. But we must also require that node i appear exactly once in the cycle.This is done by the clausesfor i = I, ...
,n and(Xijfor i, j, k = 1, ... ,n and ii-k.VXkj)304Chapter 7NP-COMPLETENESSSo far these clauses express the requirement that the xij's represent a bijection or permutation of the nodes of G. We must next express by new clauses therequirement that this permutation is indeed a cycle of C. We do this by addingthe clause(Xij V Xk,j+l)(1)for j = 1, ... , n and for each pair (i, k) of nodes such that (i, k) is not an edgeof G. Here by Xk,n+l we mean the Boolean variable Xkl; that is, addition inthe second index is assumed to be modulo n.
Intuitively, the clauses in (1) statethat, if there is no (i, k) edge in G, then it cannot be the case that i and kappear consecutively in this order in the alleged Hamilton cycle. This completesthe construction of T(G).It is easy to argue that the construction of T( G) can be carried out inpolynomial time. There are O(n3) clauses to be constructed, with a total numberof O(n3) literals.
The structure of these clauses is extremely simple, and eitherdepends on n alone, or depends on the edges of G in a rather straightforwardway. It would be straightforward to construct a polynomial-time Turing machinethat computes the function T.Next we have to argue that G has a Hamilton cycle if and only if T(G) issatisfiable. Suppose that there is a truth assignment T that satisfies T( G). SinceT must make at least one literal T in each of the clauses other than those in (1)above, it follows that T encodes a bijection on the nodes of G, that is, for each iexactly one T(xij) is T, and for each j exactly one T(xij) is T.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
