1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 75
Текст из файла (страница 75)
Still, for many NP-complete problems, in practice they often turnout to be the ones that perform best! Explaining and predicting the impressive empirical success of some of these algorithms is one of the most challengingfrontiers of the theory of computation today.Problems for Section 7.47.4.1. Give a polynomial algorithm for the DOMINATING SET problem (recall Problem 7.3.6) in the special case of trees (considered as symmetric directedgraphs).7.4.2. Suppose that all clauses in an instance of satisfiability contain at most onepositive literal; such clauses are called Horn clauses.
Show that, if allclauses of a Boolean formula are Horn clauses, then the satisfiability question for this formula can be settled in polynomial time. (Hint: When doesa variable in a Horn formula have to be assigned T?)7.4.3. Show that the TRAVELING SALESMAN PROBLEM remains NP-completeeven if the distances are required to obey the triangle inequality. (Hint:Look back at our original proof that the TRAVELING SALESMAN PROBLEMis NP-complete.)7.4.4.
Suppose that, in an instance of the traveling salesman problem with cities1,2, ... ,n and distance matrix d ij , we only consider tours that start froma, traverse by some path of length L the cities in a set T ~ {I, 2, ... ,n},end up in another city b, and then visit the remaining cities and return toa. Let us call this set of tours S.Chapter 7: NP-COMPLETENESS350(a) Foreachcityi E {1,2, ... ,n}-T-{a,b},letmi be the sum of the smallest and next-to-smallest distances from i to another city in {I, 2, ...
, n} T -{ a, b}. Let s be the shortest distances from a to any city in {I, 2, ... , n}T - {a, b}, plus the corresponding shortest distance from b. Show that anytour in S has cost at leastL1+ 2"[Lmi+ s].iE{1,2, ... ,n}-T-{ a,b}That is, the formula above is a valid lower bound for S.(b) The minimum spanning tree of the n cities is the smallest tree thathas the cities as set of nodes; it can be computed very efficiently. Derive abetter lower bound for S from this information.7.4.5. How many 2-change neighbors does a tour of n cities have? How many3-change neighbors? 4-change neighbors?7.4.6. (a) Suppose that in the simulated annealing algorithm the temperature iskept at zero.
Show that this is the basic local improvement algorithm.(b) What is the simulated annealing algorithm with the temperature keptat infinity?(c) Suppose now that the temperature is zero for a few iterations, theninfinity for a few, then zero again, etc. How is the resulting algorithmrelated to the basic version of local improvement?REFERENCESStephen A. Cook was the first to exhibit an NP-complete language in his papero S. A. Cook "The Complexity of Theorem-Proving Procedures," Proceedings ofthe Thir·d Annual ACM Symposium on the Theory of Computing pp. 151-158).New York: Association for Computing Machinery, 1971.Richard M. Karp established the scope and importance of Np-completeness in his papero R. M.
Karp "Reducibility among Combinatorial Problems," in Complexity ofComputer Computations, (pp. 85-104), ed. R. E. Miller and J. W. Thatcher.New York: Plenum Press, 1972,where, among a host of other results, Theorems 7.3.1-7.3.7, and the results in problems7.3.4 and 7.3.6, are proved. NP-completeness was independently discovered by LeonidLevin ino L. A. Levin "Universal Sorting Problems," Problemi Peredachi Informatsii, 9,3, pp.
265-266 (in Russian), 1973.The following book contains a useful catalog of over 300 NP-complete problems frommany and diverse areas; many more problems have been proved NP-complete since itsappearence.o M. R. Garey and D. S. Johnson Computers and Intractability: A Guide to theTheory of NP-completeness, New York: Freeman, 1979.References351This book is also an early source of information on complexity as it applies to concreteproblems, as well as on approximation algorithms. For much more recent and extensivetreatment of this latter subject seeo D. Hochbaum (ed.) Approximation Algorithms for· NP-hard Froblems, Boston,Mass: PWS Publishers, 1996,and for more information about other ways of coping with NP-completeness see, forexample,o C.
R. Reeves, (ed.) Modern Heuristic Techniques for Combinatorial Froblems,New York: John Wiley, 1993, ando C. H. Papadimitriou and K. Steiglitz Combinatorial Optimization: Algorithmsand Complexity Englewood Cliffs, N.J.: Prentice-Hall, 1982; second edition, NewYork: Dover, 1997.Indexalocal improvement and simulatedannealing, 345-9ambiguous grammar, 128acceptance, 57antisymmetric relation, 15by finite automata, 57, 66by nondeterministic finite automata, approximation algorithm, 335-7arguments of a function, 1166by pushdown automata, 132arithmetic progression, 89by empty store, 136by final state, 135bby Turing machines, 194by random access Turing mabacktracking algorithm, 341-3chines, 216Bar-Hillel,V., 110, 176by nondeterministic Turing mabasicfunctions,234chines, 222bijection,11accepting configuration, 194BIN PACKING, 332Aho, A.
V., 177binary alphabet, 42alphabet, 42, 116, 181binary relation, 10algorithms 2-4, 31-41binary representation of the integers,for finite automata 102-10196-7, 219-20, 284-5, 316for context-free grammars 150-8BINARYBOUNDEDTILING, 316Turing machines as - , 179, 245Bird,M.,1117blank symbol, U, 181efficient, 275-92Boolean variable, 288polynomial-time, 276-92approximation, or E-approximation, Boolean connectives, 288335--9Boolean formula, 288--9dynamic programming, 154, 334in conjunctive normal form, 288backtracking and branch-and-bound, Boolean logic, 288339-45bottom-up parsing, 169-72Index354310-2, 315-6boustrophedon language, 259Brainerd, W.
S., 244branch-and-bound algorithm, 343-5Brassard, G., 53Bratley, P., 53busy-beaver function, 253BOUNDED TILING,cCantor, G., 27, 53Cartesian product, 10certificate, or witness, 297Chomsky hierarchy, 272Chomsky, N., 175-7, 273Chomsky normal form, 151Church-Thring thesis, 245-47quantitative refinement, 276clause, 288CLIQUE, 283, 326-7, 333, 336closure, 30, :37-39closure property, 39, 75-7, 143-5Cobham, A., 299compatible transitions, 158compiler, 2, 56, 117, 162-70complement of a set, 45regular languages closed under-,76context-free languages not closedunder -,147recursive languages closed under-,199-200recursively enumerable languagesnot closed under - , 253P close4, under -, 76composite number, 223, 298-9composition of functions, 234computation, 1-4,by grammars and other systems,232by a random access Turing machine, 216-8by a Turing machine, 185, 194200concatenation of strings, 42concatenation of languages, 45configuration,of a finite automaton, 57, 66of a pushdown automaton, 131of a Thring macchine, 202-4of a random access Thring machine, 211consistent strings, 158context, 115, 228, 232context-free grammar, 114-5ambiguous, 128self-embedding, 149-s and pushdown automata, 13642LL(I), 167weak precedencl(, 173undecidability of problems about--s, 259-62context-free language, 115-75deterministic, 157inherently ambiguous 129context-sensitive language, 271Cook, S.
A., 244, 350Cook's Theorem, 312-3Cormen, T. H., 53countable set, 21count ably infinite set, 21counter machine, 258cycle in a graph, 18Euler cycle 281-2Hamilton cycle 282, 320-4dDavis, M., 243-4Davis-Putnam procedure, 342dead-end configuration, 160-1decides, 195, 216, 222355Indexdefinite language, 85definition by induction, 43derivation, 116, 228derivation, 228leftmost, 127rightmost, 127deterministic finite automaton, 57deterministic finite-state transducer,60deterministic pushdown automaton,158deterministic context-free language,159difference of sets, 7directed graph, 14disjoint sets, 8disjunctive normal form of a regularexpression, 52domain of a function, 11DOMINATING SET, 333, 349dynamic programming algorithm, 154,278,334eE-approximation algorithm, 335Earley, J., 176edge of a graph, 14Edmonds, J., 299element of a set, 5empty set, 5empty string, 42enumerating Thring machine, 268equinumerous sets, 20equivalence class, 16EQUIVALENCE OF DETERMINISTIC FINITE AUTOMATA, 286EQUIVALENCE OF NONDETERMINISTIC FINITE AUTOMATA, 286,295, 328EQUIVALENCE OF REGULAR EXPRESSIONS,287, 328equivalence relation, 16equivalent finite automata, 69equivalent strings with respect to L,94equivalent strings with respect to M,95erasing move of a Thring machine,182Euler, L., 281, 299EULER CYCLE, 281-2Eulerian graph, 281Evey, J., 176EXACT COVER, 318-21, 324-5, 331exponentially bounded Thring machine, 296[XP, or exponential time, 296-7ffalse, .1, 289fanout of a context-free grammar, 145Fermat, P.
de, 299final states, 57, 66, 131finite set, 20finite automaton, 55nondeterministic, 65two-way, 1012-head, 91, 2622-tape, 62-3finite control, 56finite-state machine, 554-change neighborhood, 347fully approximable problem, 336function, 10basic, 234defined by cases, 236defined recursively, 234primitive recursive, 234IL-recursive, 239Index356gGarey, M. R., 351generalization of a problem, 315generates, 115gadget, 320Ginsburg, S., 111, 177grammar, or unrestricted grammar,228-32grammatically computable function,232graph, 15GRAPH COLORING, 318Greibach normal form, 149Greibach, S., 177hHalmos, P., 52halted configuration, 183, 211HALTING PROBLEM, 279-80halting problem for Turing machines,251-4halting states, 181Hamilton, W.
R., 282HAMILTON CYCLE, 282-6, 292, 295,302-4, 309, 320, 323, 331,333, 338, 342-3HAMILTON PATH, 309, 331, 333HAMILTON PATH BETWEEN TWO SPECIFIED NODES, 331Harrison, M. A., 53, 177Hartmanis, J., 299height of a parse tree, 145Hennie , F. C., 243Hermes, H., 244HITTING SET, 332Hochbaum, D., 351homomorphism, 85, 148,316nonerasing, 299Hopcroft, J. E., 111, 244Horn clause, 349Ichbiah, J. D., 177identity function, 234image of a function, 11in approximable problem, 336INDEPENDENT SET, 283, 286, 292,296, 298, 301-2, 318, 3268, 332-6INDUCED SUBGRAPH ISOMORPHISM,332INEQUIVALENCE OF *-FREE REGULAREXPRESSIONS, 329INEQUIVALENCE OF REGULAR EXPRESSIONS, 328infinite set, 21inherently ambiguous language, 129initial configuration, 194, 216initial state, 56--7, 66, 131, 181in-place acceptor, or linear-boundedautomaton, 271input alphabet, 194input symbols, 131input tape, 56instructions of a random access Turing machine, 211INTEGER PROGRAMMING, 332intersection of sets, 6inverse of a function, 12JJohnson, D.
S., 351kKarp, R. M., 350Kasami, T., 176Kleene, S. C., 110, 244IndexKleene star, 45KNAPSACK, 305~7, 324~6Knuth, D. E., 53, 111, 177k-tape 'lUring machine, 202label, 123Landweber, 1. H., 244language, 44-52,regular 47~51, 77~80context-free 114-75deterministic context-free, 159~75recursive, 195, 199, 267~271recursively enumerable, 199, 267~271accepted by a finite automaton,57, 66accepted by empty store, 136accepted by final state, 135generated by a grammar, 115,228-s vs.
problems, 279~81language generator, 51, 113language recognition device, 51, 113A-change neighborhood, 347leaves of a parse tree, 123left-end symbol, [>, 181left factoring, 165left recursion, 166left-linear grammar, 122leftmost derivation, 127Leiserson, C. E., 53length,of a sequence 10,of a path, 18,of a string 42,of a computation 132, 145, 185of a derivation 116Levin, L. A., 350357Lewis, P. M., II, 177lexicographic enumeration, 269lexicographic ordering, 44lexicographically 'lUring-enumerablelanguage, 269Lin-Kernighan algorithm, 347linear, 143linear-bounded automaton, 271literal, positive and negative, 288Liu, C. L., 52LL(l) grammar, 167LONGEST CYCLE, 332mMachtey, M., 244Markov, A.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
