Chapter 0 Preface¶
Chapter 1 Graphs¶
Chapter 2 Limits to Computing¶
- 2.1. Limits to Computing
- 2.2. Reductions
- 2.3. NP-Completeness
- 2.4. Circuit Satisfiability
- 2.5. Formula Satisfiability
- 2.6. 3-CNF Satisfiability
- 2.7. The Clique Problem
- 2.8. The Independent Set Problem
- 2.9. The Vertex Cover Problem
- 2.10. The Hamiltonian Cycle Problem
- 2.11. The Traveling Salesman Problem
- 2.12. NP-Completeness Proofs
- 2.13. Reduction of Circuit SAT to SAT
- 2.14. Reduction of SAT to 3-SAT
- 2.15. Reduction of 3-SAT to Clique
- 2.16. Reduction of Clique to Independent Set
- 2.17. Reduction of Independent Set to Vertex Cover
- 2.18. Reduction of 3-SAT to Hamiltonian Cycle
- 2.19. Reduction of Hamiltonian Cycle to Traveling Salesman
- 2.20. Coping with NP-Complete Problems
- 2.21. Unsolveable Problems
- 2.22. Turing Machines
