Theoretical Computer Science

A.Y. 2025/2026
6
Max ECTS
48
Overall hours
SSD
INF/01
Language
Italian
Learning objectives
The course introduces basics of computability and complexity theory, presenting suitable theoretical tools which also turn out to be useful to rigorously approach several other issues in computer science. The notion of algorithmically solvable problem is formally characterized, as well as the class of unsolvable problems analyzed. Next, problems are investigated, on the basis of computational resource requirements for algorithmic solution, rigorously defining the notion of algorithmic efficiency. In this realm, the celebrated P = NP question is tackled.
Expected learning outcomes
The student will acquire tools and techniques in computability and complexity theory, which are fundamental in any research investigation in computer science and, more generally, in the rigorous analysis of problems and their algorithmic solutions. She/he will be able first to correctly state and model problems, and then formally investigate algorithmic solutions from several viewpoints.
Single course

This course cannot be attended as a single course. Please check our list of single courses to find the ones available for enrolment.

Course syllabus and organization

Single session

Responsible
Lesson period
First four month period
Course syllabus
Computability Theory
· Mathematical basics
· Cantor's pair function
· RAM and while programming languages
· Syntax and operational semantics
· Compilers
· Program encoding by numbers
· Interpreter and universal function
· "goto" elimination
· Partial recursive functions
· Church's thesis
· Undecidable problems
· Authomatic parameter passing
· Acceptable programming systems
· Recursion theorem
· Recursive and recursively enumerable sets
· Closure properties
· Rice's theorem

Complexity Theory
· Introducing complexity theory
· Mathematical basics: "big O" notation
· Deterministic Turing machines
· Computational resources: time and space
· Time and space complexity classes
· The classes L, P, PSPACE
· Restricted Church's thesis
· Noneterministic Turing machines: time and space
· The classes NL, NP, NPSPACE
· Savitch's theorem
· Reductions among problems and completeness
· NP, P, PSPACE-complete problems
· Cook's theorem and examples of reductions
Prerequisites for admission
No particular prerequisite required.
Teaching methods
The course consists of traditional lectures in which, first of all, mathematical basics are presented. Such basics will enable a precise formalizations of the foundation of Computability Theory and Complexity Theory. Beside notions related to these two disciplines, exercises and problems will be illustrated aiming at consolidating theory and stimulating the interest in more advanced topics which require and develop a certain scientific maturity.
Teaching Resources
Textbooks:
· Handouts and slides available at the course website (see below)
· Computability Theory:
- A.J. Kfoury, R.N. Mall, M.A. Arbib. Programmazione e computabilità. Etas libri, 1986. (Available also in English)
· Complexity Theory:
- M.R. Garey, D.S. Johnson. Computers and intractability. A guide to the theory of NP-completeness. W.H. Freeman, 1979.

Website:
- course website on myAriel university platform
Assessment methods and Criteria
The final examination consists in an oral colloquium which covers the whole span of topics proposed during the course of Theoretical Computer Science. Questions will be proposed, on both parts characterizing the course, i.e., Computability Theory and Complexity Theory. Questions will aim to check students' knowledge of basic concepts as well as the ability of provide precise formalization of problems and solutions. In addition, some problems will be issued requiring "original" ideas from the students, in order to appreciate a certain level of scientific maturity. About forty minutes will be devoted to the oral colloquium. The exam will be rated from 1 to 30. An evaluation between 18 and 23 indicates an appropriate level of knowledge of basics of theoretical computer science, an evaluation between 24 and 27 indicates a good knowledge of such basics, higher evaluations indicate a very good knowledge and originality in applying basics in theoretical computer science.
INF/01 - INFORMATICS - University credits: 6
Lessons: 48 hours
Professor: Mereghetti Carlo
Professor(s)
Reception:
On appointment, via email
Room S 6008, VI floor, Dip. Informatica "Giovanni Degli Antoni", via Celoria 18, 20133 Milano, Italy