Computers and intractability : A guide to the theory of NP-completeness
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Livre papier |
| Lenguaje: | Anglais |
| Publicado: |
New York, N.Y :
W. H. Freeman
C 1979.
|
| Colección: | A series of books in the mathematical sciences / Victor Klee, editor
|
| Materias: | |
| Nota: |
Autres tirages : 1999, 2000, 2002, 2003, 2008 |
| Autres localisations: | Voir dans le Sudoc |
| Variante du titre: | NP-completeness |
Tabla de Contenidos:
- 1. Computers, complexity, and intractability
- 1.1 Introduction
- 1.2 Problems, algorithms, and complexity
- 1.4 Provably intractable problems
- 1.5 NP-complete problems
- 1.6 An outline of the book
- 2. The theory of NP-completeness
- 2.1 Decision problems, languages, and encoding schemes
- 2.2 Deterministic Turing machines and the class P
- 2.3 Nondeterministic computation and the class NP
- 2.4 The relationship between P and NP
- 2.5 Polynomial transformations and NP-completeness
- 2.6 Cook's theorem
- 3. Proving NP-completeness results
- 3.1 Six basic NP-complete problems
- 3.2 Some techniques for proving NP-completeness
- 3.3 Some suggested exercises
- 4. Using NP-completeness to analyze problems
- 4.1 Analyzing subproblems
- 4.2 Number problems and strong NP-completeness
- 4.3 Time complexity as a function of natural parameters
- 5. NP-hardness
- 5.1 Turing reducibility and NP-hard problems
- 5.2 A terminological history
- 6. Coping with NP-complete problems
- 6.1 Performance guarantees for approximation algorithms
- 6.2 Applying NP-completeness to approximation problems
- 6.3 Performance guarantees and behavior "in practice"
- 7. Beyond NP-completeness
- 7.1 The structure of NP
- 7.2 The polynomial hierarchy
- 7.3 The complexity of enumeration problems
- 7.4 Polynomial space completeness
- 7.5 Logarithmic space
- 7.6 Proofs of intractability and P vs. NP
- Appendix : a list of NP-complete problems
- A1. Graph theory
- A2. Network design
- A3. Sets and partitions
- A4. Storage and retrieval
- A5. Sequencing and scheduling
- A6. Mathematical programming
- A7. Algebra and number theory
- A8. Games and puzzles
- A9. Logic
- A10. Automata and language theory
- A11. Program optimization
- A12. Miscellaneous
- A13. Open problems