73093 - Theoretical Informatics (1) (LM)

Course Unit Page

Academic Year 2018/2019

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