8. NP-Completeness
Complexity of problems. Problems as strings. Encoding of
strings. Languages. Decision problems as language
recognition. Turing Machines. NP-Hardness. NP-Completeness.
Polynomial-time reductions. Cook-Levin Theorem. NPC
problems. Approximations algorithms.