Computer and intractability: a guide to the theory of NP-completeness

Cover......Page __sk_0000.djvu
Copyright......Page __sk_0002.djvu
Contents......Page __sk_0003.djvu
Preface......Page __sk_0007.djvu
1.1 Introduction......Page __sk_0011.djvu
1.2 Problems, Algorithms, and Complexity......Page __sk_0014.djvu
1.3 Polynomial Time Algorithms and Intractable Problems......Page __sk_0016.djvu
1.4 Provably Intractable Problems......Page __sk_0021.djvu
1.5 NP-Complete Problems......Page __sk_0023.djvu
1.6 An Outline of the Book......Page __sk_0024.djvu
2 The Theory of NP-Completeness......Page __sk_0027.djvu
2.1 Decision Problems, Languages, and Encoding Schemes......Page __sk_0028.djvu
2.2 Deterministic Turing Machines and the Class P......Page __sk_0033.djvu
2.3 Nondeterministic Computation and the Class NP......Page __sk_0037.djvu
2.4 The Relationship Between P and NP......Page __sk_0042.djvu
2.5 Polynomial Transformations and NP-Completeness......Page __sk_0044.djvu
2.6 Cook\'s Theorem......Page __sk_0048.djvu
3 Proving NP-Completeness Results......Page __sk_0055.djvu
3.1 Six Basic NP-Complete Problems......Page __sk_0056.djvu
3.1.1 3-SATISFIABILITY......Page __sk_0058.djvu
3.1.2 3-DIMENSIONAL MATCHING......Page __sk_0060.djvu
3.1.3 VERTEX COVER and CLIQUE......Page __sk_0063.djvu
3.1.4 HAMILTONIAN CIRCUIT......Page __sk_0066.djvu
3.1.5 PARTITION......Page __sk_0070.djvu
3.2.1 Restriction......Page __sk_0073.djvu
3.2.2 Local Replacement......Page __sk_0076.djvu
3.2.3 Component Design......Page __sk_0082.djvu
3.3 Some Suggested Exercises......Page __sk_0084.djvu
4 Using NP-Completeness to Analyze Problems......Page __sk_0087.djvu
4.1 Analyzing Subproblems......Page __sk_0090.djvu
4.2 Number Problems and Strong NP-Completeness......Page __sk_0100.djvu
4.2.1 Some Additional Definitions......Page __sk_0102.djvu
4.2.2 Proving Strong NP-Completeness Results......Page __sk_0105.djvu
4.3 Time Complexity as a Function of Natural Parameters......Page __sk_0116.djvu
5.1 Turing Reducibility and NP-Hard Problems......Page __sk_0119.djvu
5.2 A Terminological History......Page __sk_0128.djvu
6 Coping with NP-Complete Problems......Page __sk_0131.djvu
6.1 Performance Guarantees for Approximation Algorithms......Page __sk_0133.djvu
6.2 Applying NP-Completeness to Approximation Problems......Page __sk_0147.djvu
6.3 Performance Guarantees and Behavior \"In Practice\"......Page __sk_0158.djvu
7 Beyond NP-Completeness......Page __sk_0163.djvu
7.1 The Structure of NP......Page __sk_0164.djvu
7.2 The Polynomial Hierarchy......Page __sk_0171.djvu
7.3 The Complexity of Enumeration Problems......Page __sk_0177.djvu
7.4 Polynomial Space Completeness......Page __sk_0180.djvu
7.5 Logarithmic Space......Page __sk_0187.djvu
7.6 Proofs of Intractability and P vs. NP......Page __sk_0191.djvu
Appendix: A List of NP-Complete Problems......Page __sk_0197.djvu
A1.1 Covering and Partitioning......Page __sk_0200.djvu
A1.2 Subgraphs and Supergraphs......Page __sk_0204.djvu
A1.3 Vertex Ordering......Page __sk_0209.djvu
A1.4 Iso- and Other Morphisms......Page __sk_0212.djvu
Al.5 Miscellaneous......Page __sk_0213.djvu
A2.1 Spanning Trees......Page __sk_0216.djvu
A2.2 Cuts and Connectivity......Page __sk_0219.djvu
A2.3 Routing Problems......Page __sk_0221.djvu
A2.4 Flow Problems......Page __sk_0224.djvu
A2.5 Miscellaneous......Page __sk_0228.djvu
A3.1 Covering, Hitting, and Splitting......Page __sk_0231.djvu
A3.2 Weighted Set Problems......Page __sk_0233.djvu
A4.1 Data Storage......Page __sk_0236.djvu
A4.2 Compression and Representation......Page __sk_0238.djvu
A4.3 Database Problems......Page __sk_0242.djvu
A5.1 Sequencing on One Processor......Page __sk_0246.djvu
A5.2 Multiprocessor Scheduling......Page __sk_0248.djvu
A5.3 Shop Scheduling......Page __sk_0251.djvu
A5.4 Miscellaneous......Page __sk_0253.djvu
A6 Mathematical Programming......Page __sk_0255.djvu
A7.1 Divisibility Problems......Page __sk_0259.djvu
A7.2 Solvability of Equations......Page __sk_0260.djvu
A7.3 Miscellaneous......Page __sk_0262.djvu
A8 Games and Puzzles......Page __sk_0264.djvu
A9.1 Propositional Logic......Page __sk_0269.djvu
A9.2 Miscellaneous......Page __sk_0271.djvu
A10.1 Automata Theory......Page __sk_0275.djvu
AlO.2 Formal Languages......Page __sk_0277.djvu
A11.1 Code Generation......Page __sk_0282.djvu
Al1.2 Programs and Schemes......Page __sk_0285.djvu
A12 Miscellaneous......Page __sk_0289.djvu
A13 Open Problems......Page __sk_0295.djvu
Symbol Index......Page __sk_0299.djvu
Reference and Author Index......Page __sk_0301.djvu
Subject Index......Page __sk_0337.djvu
Update for the Current Printing......Page __sk_0349.djvu