Chapter 0 Preface¶
Chapter 1 Introduction¶
Chapter 2 Analyzing Problems: The Basics¶
Chapter 3 Searching¶
Chapter 4 Lower Bounds¶
Chapter 5 Number Problems¶
Chapter 6 Probabilistic Algorithms¶
Chapter 7 Miscellaneous¶
Chapter 8 Limits to Computing¶
- 8.1. Limits to Computing
- 8.2. Reductions
- 8.3. NP-Completeness
- 8.4. NP-Completeness Proofs
- 8.5. Circuit Satisfiability
- 8.6. Formula Satisfiability
- 8.7. 3-CNF Satisfiability
- 8.8. The Clique Problem
- 8.9. The Independent Set Problem
- 8.10. The Vertex Cover Problem
- 8.11. The Hamiltonian Cycle Problem
- 8.12. The Traveling Salesman Problem
- 8.13. Reduction of Circuit SAT to SAT
- 8.14. Reduction of SAT to 3-SAT
- 8.15. Reduction of 3-SAT to Clique
- 8.16. Reduction of Independent Set to Vertex Cover
- 8.17. Reduction of 3-SAT to Hamiltonian Cycle
- 8.18. Reduction of Clique to Independent Set
- 8.19. Reduction of Hamiltonian Cycle to Traveling Salesman
- 8.20. Coping with NP-Complete Problems
- 8.21. Unsolveable Problems
- 8.22. Turing Machines
