Theoretical Computer Science
A.Y. 2025/2026
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.
Lesson period: First four month period
Assessment methods: Esame
Assessment result: voto verbalizzato in trentesimi
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
· 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
· 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.
Professor(s)
Reception:
On appointment, via email
Room S 6008, VI floor, Dip. Informatica "Giovanni Degli Antoni", via Celoria 18, 20133 Milano, Italy