Here is the detailed list of subjects from Chapter 10 that we have presented in class and that will be matter of evaluation at the finals.
Chapter 10: Intractable problems.
Computational complexity of a TM. Definition of the class deterministic polynomial time (P) and the class non-deterministic polynomial time (NP). Polynomial time reductions. NP-complete problems and NP-hard problems. Boolean expressions and their encoding. Satisfiability of Boolean expressions and the SAT problem. Cook theorem: SAT is NP-complete (first part of the proof only: SAT is in NP). Normal forms for Boolean expressions. CSAT and 3SAT are NP-complete (statement only, no proof). Definitions of independent sets and of the IS problem. IS is NP-complete. Definitions of node cover and of the NC problem. NC is NP-complete (statement only, no proof). Definitions of directed Hamiltonian circuit and of the DHC problem. DHC is NP-complete (statement only, no proof). Other NP-complete problems.
Skip: Second part of the proof of Theorem 10.9; Sections 10.3.2, 10.3.3, and 10.3.4; proofs of Theorems 10.21, 10.23, and 10.24.