Computability: enumerability, computability, decidability; primitive recursive functions and relations; Ackermann function, mu-recursive functions, Church thesis; Turing machines, the halting problem, universal Turing machine; problem reduction, Rice theorem.
Complexity: tractability and intractability; the classes P and NP; polynomial-time reduction, NP-completeness; Cook theorem; NP-complete problems; further complexity classes; space complexity.
- Massimiliano Goldwurm, Introduzione ai Problemi NP-completi, http://homes.di.unimi.it/goldwurm/algo/npcomp.pdf.
- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley.
- Daniele Mundici, Dalla macchina di Turing a P/NP, McGraw-Hill.
- Michael Sipser, Introduzione alla teoria della computazione, Maggioli Editore.
- Thomas A. Sudkamp, Languages and Machines, Addison-Wesley.
Learning Objectives
KNOWLEDGE AND UNDERSTANDING - Scope of the course is to illustrate the notion of algorithm, describing different formalizations in detail (recursive dunctions and Turing machines). Moreover, the structural complexity of algorithms will be investigated, that is, for a given amount of resources, we will describe the class off problems which can be solved algorithmically and using at most such an amount.
APPLYING KNOWLEDGE AND UNDERSTANDING - At the end of the course the student is going to acquire basic knowledge of computability and complexity theory and will be able to solve medium level problems in such disciplines. Moreover, the student will have enough tools to deepen her/his knowledge of the subject, in order to tackle more advanced problems.
Prerequisites
Algorithms and Data Structures, Discrete Mathematics and Mathematical Logics, Programming, Computer Architecture
Teaching Methods
Class lessons
Further information
Attendance: recommended.
Office hours: by appointment, using email (luca.ferrari@unifi.it) or phone (055 2751484).
Type of Assessment
Written exam (one question concerning computability, one question concerning complexity); oral exam (one question concerning computability, one question concerning complexity). The final grades will be determined by the grades of the written exam (50%) and the oral exam (50%).
Course program
Computability theory: enumerability, computability, decidability; primitive recursive function; primitive recursive relations; Ackermann function, mu-recursive functions, Church thesis; Turing machines, tau-recursive functions; Turing machines as language acceptors; the halting problem, universal Turing machine; problem reduction, Rice theorem.
Complexity theory: time complexity of a Turing machine; tractable and intractable problems; the classes P and NP; polynomial-time reduction and NP-completeness; Cook theorem; examples of NP-complete problems; primality tests; further complexity classes: the classes co-NP, EXP and NEXP; space complexity, Savitch theorem; complexity of counting: the classes FP and #P.