B9045 - COMPLESSITA' COMPUTAZIONALE E DESCRITTIVA

Learning outcomes

This course will provide an introduction to Computational Complexity, Descriptive Complexity, and Borel Complexity. The goal of Computational Complexity is to measure the complexity of solving a given problem algorithmically, in terms of the "space" and "time" resources needed for the computation to run on a given input. Descriptive Complexity studies how complicated it is to describe a set or a relation in terms of formulae of a given complexity. Borel Complexity allows one to measure the complexity of sets or functions on the real line (or some other topological space), and of classification problems. In this context, the complexity of a set is defined as how complicate a description of the given set in terms of open sets, by taking countable unions, intersections, and complements, must be. These subjects are closely connected, and have a number of applications to several mathematical subjects (algebra, analysis, discrete mathematics). This course will provide an overview of such applications. At the end of the course, the student will be familiar with the fundamental notions of Computational, Descriptive, and Borel Complexity Theory, and will be able to apply such notions to study the compleixty of algorithmic and classification problems.

Course contents

This course provides an introduction to Computational, Descriptive, and Borel Complexity, and interactions between these subjects.

Particularly, the course will cover the following topics, in roughly this order:

1. Review of models of computations (Turing Machines)
2. Introduction to Computational Complexity
3. Complexity Classes
4. Review of syntax and semantics in logic
5. Introduction to Descriptive Complexity
6. Semantic description of complexity classes
7. Review of Borel sets and functions
8. Borel complexity of sets and classification problems

Readings/Bibliography

As references, the students can consult the following sources:

• Sipser, Michael. Introduction to the Theory of Computation
• Arora, Sanjeev; Barak, Boaz, Computational complexity. A modern approach. Cambridge University Press, Cambridge, 2009. xxiv+579
• Grohe, Martin, Descriptive complexity, canonisation, and definable graph structure theory. Lecture Notes in Logic, 47. Association for Symbolic Logic, Ithaca, NY; Ca mbridge University Press, Cambridge, 2017
• Gao, Su. Invariant descriptive set theory. 
  Pure and Applied Mathematics (Boca Raton), 293. CRC Press, Boca Raton, FL, 2009. xiv+383
• Kechris, Alexander S. Classical descriptive set theory. Graduate Texts in Mathematics, 156. Springer-Verlag, New York, 1995. xviii+402 pp.

Teaching methods

The course will be delivered through 48 hours of frontal lectures, dedicated to the discussion of the material as well as problems. Furthermore, practice problems will be given to students to verify their understanding of the course, and to practice solving problems.

Assessment methods

The assessment for the course consists in an oral exam.

This exam aims at assessing the comprehension of the topics covered in the course, and the ability of the student to apply them in the solution of problems.

Teaching tools

On the online platform Virtuale, the students will find:

• for each topic, the corresponding chapters or sections of the recommended texbooks;
• practice problems list, to be solved independently for practice;
• a syllabus containing the list of all the topics in the course.

Office hours will be by appointment, either in person or online.

Office hours

See the website of Martino Lupini