Chapter 0 Preface¶
Chapter 1 Introduction¶
Chapter 2 Analyzing Problems: The Basics¶
Chapter 3 Searching¶
Chapter 4 Lower Bounds¶
Chapter 5 Dynamic Programming¶
Chapter 6 Limits to Computing¶
- 6.1. Limits to Computing
- 6.2. Reductions
- 6.3. NP-Completeness
- 6.4. NP-Completeness Proofs
- 6.5. Circuit Satisfiability
- 6.6. Formula Satisfiability
- 6.7. 3-CNF Satisfiability
- 6.8. Reduction of SAT to 3-SAT
- 6.9. The Clique Problem
- 6.10. The Independent Set Problem
- 6.11. The Vertex Cover Problem
- 6.12. The Hamiltonian Cycle Problem
- 6.13. The Traveling Salesman Problem
- 6.14. Reduction of Circuit SAT to SAT
- 6.15. Reduction of 3-SAT to Clique
- 6.16. Reduction of Independent Set to Vertex Cover
- 6.17. Reduction of 3-SAT to Hamiltonian Cycle
- 6.18. Reduction of Clique to Independent Set
- 6.19. Reduction of Hamiltonian Cycle to Traveling Salesman
- 6.20. Coping with NP-Complete Problems
- 6.21. Unsolveable Problems
- 6.22. Introduction to Turing Machines
- 6.23. Turing Machines: Advanced Topics
