1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 71
Текст из файла (страница 71)
,x n }. In this interpretation, L( D:i) is precisely the set of all truthassignments that fail to satisfy Gi . Thus L(Rd is the set of all truth assignments that fail to satisfy at least one of the clauses of the given Boolean formula.Thus, the given Boolean formula is satisfiable if and only if L(RI) is differentfrom {O, I}n -which is precisely L(R 2 ). The proof is complete . •The equivalence problem for general regular expressions and for nondeterministic finite automata can, of course, only be harder (see the references forinformation about their precise complexity), and similarly for the state minimization problems for nondeterministic finite automata.
None of these simplystated problems about t.he most primitive of computational modds can be solvedefficiently unless P = Np.But how about the following less ambitious goal: Suppose that we wish,given a nondeterministic finite automaton, to find the equivalent deterministicone with the minimum number of states. We know that any such algorithmmust be exponential in the worst. case because the output may have to be exponentially long in the size of the input (recall Example 2.5.4). But is there analgorithm that runs in time polynomial in t.he size of the input and the output?Such an algorithm would spend exponential time when the output is large, butwould swiftly output small automata. (The obvious algorithm which first carries out the subset construction and then minimizes the resulting deterministicaut.omaton does not qualify, because the subset construction may yield an intermediate result that is exponentially large, even though the final output -theminimum equivalent deterministic automaton- may be polynomial.)Unfortunately, we can show that even such an algorithm is unlikely to exist:Corollary:Unless P = NP, there is no algorithm which, given a regularexpression or a nondeterministic finite automaton, constructs the minimumstate equivalent deterministic finite automaton in time that is polynomial in theinput and the output.Proof: Let A1n denote the simple n+ I-state finite aut.omaton accepting {O, 1 }n.In the reduction in the proof of the theorem, the given Boolean formula withn variables is unsatisfiable if and only if the minimum-state deterministic finiteaut.omaton equivalent to RI is exactly Mn.Suppose now that an algorithm as described in the statement.
of the corollaryexists, with a time bound of the form p(lxl + lyD, where P is a polynomial, X is the7.3: More NP-complete Problems331input of the algorithm, and y is its output. Then we could solve SATISFIABILITYas follows.Given any Boolean formula F with n variables, we first perform the reduction described in the proof of the theorem to obtain a regular expression R I .Then we run, on input R I , the purported algorithm for P(IRII + IMnl) steps,where IMnl is the length of the encoding of Mn. If the algorithm terminateswithin the allotted time, then we know how to answer the original SATISFIABILITY question: We answer "no" if the output is ]l.In , and we answer "yes" inthe event of any other output.
If, however, the algorithm does not halt afterp(IRII + IMnU steps, and since we know that it always halts after p(lxl + Iyl)steps, we can conclude that its output would be longer than IMnl. Hence the algorithm's output is not M n , and we can confidently answer "yes" to the originalSATISFIABILITY question.What we described in the previous paragraph is a polynomial-time algorithm for SATISFIABILITY-the time bound p(IRll + 1M!) is polynomial in thesize of the Boolean formula F. Since SATISFIABILITY is NP-complete, we mustconclude by Theorem 7.1.1 that P = NP, completing the proof.•Problems for Section 7.37.3.1.
(a) Show that EXACT COVER remains NP-complete even if all sets have nomore than three elements, and each element appears in at most three sets.(b) What happens if either number is two?7.3.2. Give the full graph (without the abbreviation of the exclusive-or gadget)that would result from the reduction from EXACT COVER to HAMILTON CYCLE if the given instance of EXACT COVER consists of the universe {Ul, U2}and the family of sets :F = {{ uI}, { UI, U2}}'7.3.3. (a) Show that the HAMILTON PATH problem is NP-complete, (1) by reducing the HAMILTON CYCLE problem to it; (2) by modifying slightly theconstruction in the proof of Theorem 7.3.2.(b) Repeat for the problem HAMILTON PATH BETWEEN TWO SPECIFIEDNODES (the obvious definition).7.3.4.
Each of the following problems is a generalization of an NP-completeproblem, and is therefore NP-complete. That is, if certain parameters ofthe problem are fixed in a certain way, then the problem in hand becomesa known NP-complete problem (recall the proof of Theorem 7.2.4).
Onecan reduce any problem to its generalization by simply introducing a newparameter, and otherwise leaving the instance as it is.For each of the problems below, prove that it is NP-complete by showingthat it is the generalization of an NP-complete problem. Give the appropriate parameter restriction in each case.Chapter 7: NP-COMPLETENESS332(a) LONGEST CYCLE: Given a graph and integer K, is there a cycle, withno repeated nodes, of length at least K? (Hint: What happens to thisproblem if K is restricted to be equal to the number of nodes of thegraph?)(b) SUBGRAPH ISOMORPHISM: Given two undirected graphs G and H, isG a subgraph of H? (That is, if G has nodes VI, ...
, V n , can youfind distinct nodes 11,1, .. . ,Un in H such that [Ui, Uj 1is an edge in Hwhenever [Vi, Vj] is an edge in G?)(c) INDUCED SUBGRAPH ISOMORPHISM: Given two undirected graphs Gand H, is G an induced sub graph of H? (That is, if G has nodesVI, ... , V n , can you find distinct nodes 11,1, ... , Un in H such that [Ui' Uj]is an edge in H if and only if [Vi, Vj] is an edge in G?)(d) RELIABLE GRAPH: Given an undirected graph G with nodes VI, ... ,Vn ,an n x n symmetric matrix Rij of natural numbers, and an integer B,is there a set S of B edges of G with the following property: Betweennodes Vi ::j:.
Vj there are at least Rij disjoint paths (that is, paths sharingno other node except for the endpoints) with edges in S. (Hint: Whathappens if Rij = 2 for all i,j, and B = n?)(e) INTEGER PROGRAMMING: Given m equationsnLaij x j= bi ,i = 1, ... , mi=1(f)(g)(h)(i)in n variables, with integer coefficients aij and bi , does it have a solutionin which all xi's are either zero or one? (Actually, this is a commongeneralization of many of the NP-complete problems we have seen;how many can you find?)TAXICAB RIPOFF: Given a directed graph G with positive lengths dijon its edges, two nodes 1 and n, and an integer K, is there a path from1 to n, not repeating any node twice, with total length K or more?HITTING SET: Given a family of sets {SI, S2, ...
, Sn}, and an integerB, is there a set H with B or fewer elements such that H intersects allsets in the family?BIN PACKING: Given a set of positive integers A. = {al, ... , an}, andtwo more integers Band K, can the integers in A. be partitioned intoB subsets ("bins") such that the numbers in each bin sum up to K orless?SET COVER: Given a family :F of subsets of a universe U, and an integerK, are there K sets in :F whose union equals U?7.3.5. Show that INDEPENDENT SET remains NP-complete even if the size Kof the INDEPENDENT SET sought equals n/21, where n is the number ofnodes.r7.4: Coping with NP-completeness3337.3.6. Show that the following problem is NP-complete.
DOMINATING SET: Givena directed graph G and an integer B, is there a set S of B nodes of G suchthat for every node u ~ S of G, there is a node v E S such that (v, u) is anedge of G.7.3.7. Call a nondeterministic finite automaton M = (K,~,~, s, F) acyclic ifthere is no state q and string w =I- e such that (q, w) ~M (q, e). Show thatthe problem of telling whether two acyclic nondeterministic finite automataare inequivalent is NP-complete.B(OPING WITH NP-(OMPLETENESSProblems do not go away when they are proved NP-complete. But once weknow that the problem we are interested in is an NP-complete problem, we aremore willing to lower our sights, to settle for solutions that are less than perfect,for algorithms that are not always polynomial, or do not work on all possibleinstances. In this section we review some of the most useful maneuvers of thissort.Special CasesOnce our problem has been shown NP-complete, the first question to ask isthis: Do we really need to solve this problem in the full generality in which itwas formulated -and proved NP-complete? NP-completeness reductions oftenproduce instances of the problem that are unnaturally complex.
Perhaps whatwe really need to solve is a more tractable special case of the problem.For example, we have already seen that there is an important special caseof SATISFIABILITY that can be easily solved efficiently: 2-SATISFIABILITY (recallSection 6.3). If all instances of SATISFIABILITY that we must solve have clausesof this kind, then the fact that the general problem is NP-complete is ratherirrelevant. But often a special case of interest turns out to be itself NP-complete-for example, 3-SATISFIABILITY is such a case, recall Theorem 7.2.3.
We nextsee another example.Example 7.4.1: Most problems involving undirected graphs become easy whenthe graph is a tree -that is to say, it has no cycles, see Figure 7-12. Lookingback at our collection of NP-complete graph problems, HAMILTON CYCLE is ofcourse trivial in trees (no tree has a cycle, Hamilton or otherwise), but so isHAMILTON PATH -a tree has a Hamilton path only if it is a Hamilton path.The CLIQUE problem also becomes trivial-no tree can have a clique with morethan two nodes.The INDEPENDENT SET problem is also easy when the graph is a tree. Themethod used for its solution takes advantage of the "hierarchical structure" of334Chapter 7: NP-COMPLETENESStrees. It is often useful in a tree to pick an arbitrary node and designate it asthe root (see Figure 7-12); once this has been done, each node u in the treebecomes itself the root of a subtree T( u) -the set of all nodes v such that the(unique) path from v to the root goes through u; see Figure 7-12.
Then problemscan be solved bottom up, by going from the leaves (subtrees with one node) tolarger and larger subtrees, until the whole tree (the subtree of the root) hasbeen dealt with. For each node u we can define the set of its children C (u) -thenodes in its subtree that are adjacent to it, excluding u itself-- and its set ofgrandchildren G(u) -the children of its children. Naturally, these sets could beempty. For example, in Figure 7-12, the root, denoted r, has two children andfive grandchildren. Nodes with no children are called leaves.(1) (1)(1) (1) (1)Figure 7-12The size of the largest independent set of the tree can now be found bycomputing, for each node u, the number I(u), defined to be the size of thelargest independent set of T( u).
It is easy to see that the following equationholds:(2)I(u) = maxiI(v), 1 +I(unLLvEC'(,,)vEG(,,)What this equation says is that, in designing the largest independent set ofT(u),we have two choices: Either (this is the first term in the max) we do not putu into the independent set, in which case we can put together all maximumindependent sets in the subtrees of its children, or (and this is the second term)we put u in the independent set, in which case we must omit all its children, andassemble the maximum independent sets of the subtrees of all its grandchildren.It is now easy to see that a dynamic programming algorithm can solve theINDEPENDENT SET problem in the special case of trees in polynomial time. Thealgorithm starts at the leaves (where I(u) is trivially one) and computes I(u) for7.4: Coping with NP-completeness335larger and larger subtrees.
The value of I at the root is the size of the maximumindependent set of the tree. The algorithm is polynomial, because for each nodeu, all we have to do is compute the expression in (2), which only takes lineartime. For example, in the tree of Figure 7-12, the values of l(u) are shown inparentheses. The largest independent set of the tree has size 14.Needless to say, the closely related NODER COVER problem can also besolved the sarre way (recall the reductions between NODE COVER and INDEPENDENT SET).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
