- Docente: Andrea Asperti
- Credits: 12
- SSD: INF/01
- Language: Italian
- Teaching Mode: Traditional lectures
- Campus: Bologna
-
Corso:
First cycle degree programme (L) in
Computer Science (cod. 8009)
Also valid for Second cycle degree programme (LM) in Philosophical Sciences (cod. 8773)
Learning outcomes
The student will learn the main notions and results of
Computability and Complexity Theory.
At the end of course the student will be aware of the theoretical
and practical limits of computation, and will be able to use and
apply methodologies and techniques typical of formal methods to the
study and solution of a wide range of algorithmic problems.
Course contents
The programma is essentially divided in two modules, respectively
devoted to Computability and Complexity Theory.
Computability:
Subrecursive languages: primitve recursion, system T;
incompleteness of total formalisms;
Turing Machines and equivalent models of computations;
Church Thesis.
The halting problem and other undecidable problems; Rice
Theorem.
Recursive and recursively enumerable sets; the Rice-Shapiro
Theorem.
Kleene's fixed point theorems.
Reducibility; productive, creative, immune and simple
sets.
Computability and (in)completeness.
Complexity:
Computational problems;
Machines Models and Complexity Measures;
Complexity Classes and their hierarchy; major classes;
reduction;
P vs NP and other open problems;
Oracle machines and the polynomial hierarchy.
Readings/Bibliography
Notes by the teacher.
Additional texts:
S.Arora, B.Barak. Computational Complexity: a modern approach.
Cambridge University Press, 2009.
Complexity: C. H. Papadimitriou. Computational Complexity. Addison
Wesley, 1994.
Assessment methods
Written and oral examination.
Office hours
See the website of Andrea Asperti