Turing machines, definitions and examples. Variations of the basic model. Multi-tape Turing machines, Non-deterministic Turing machines, Enumerators. Equivalence between different computation models. The definition of algorithm. Definition of Turing machine inputs.
Decidability. Decidable languages. The halting problem. The diagonalization method. Proof of undecidability of the halting problem. Reductions. Other undecidable languages. Undecidability proofs through reductions. Mapping reducibility. Computable functions. Definitions, basic theorems, examples. Proofs of language unrecognizability.
Measuring time complexity. Analysis of algorithms. Complexity relationships among different models. The class P. Polynomial-time deterministic Turing machines. Examples. The class NP. Non-deterministic Turing machines. Polynomia-time verifiers. Examples of problems of NP. The P versus NP question. Polynomial-time reductions, NP-completeness, definitions. The Cook-Leven Theorem. NP-completeness proofs. Satisfiability. Computing cliques in graphs. The vertex cover problem. The Hamiltonian path problem. The subset sum problem. Other NP-complete problems.
.