Massimo Lauria
- massimo.lauria@uniroma1.it
- +39-06-49910496
- Room 9 - 4^{th} floor - Dip.Science Statistiche
- Office hours: Thu 11.00-13.00 (write email first)
Respectively in buildings G and E, in Viale Regina Elena, 295.
The course should start on September 25th, and go on until December 21st. There is a Google Calendar of the lectures.
Computational complexity studies the intractability and the inherent complexity of computational problems. Some problems have efficient algorithms and solutions, while some others seem not to have any. While this could just be due to the lack of creativity, there are problems for which it is conjectured that such efficient algorithms do not exists at all.
In this course we study several computational model in which we can say interesting things about problems, in order to characterize their hardness. We discuss the famouse P vs NP problem.
The course has a strong mathematical flavor and requires mathematical maturity and some confidence with combinatorial and probabilistic methods. It is also useful to have had some preliminary exposure to algorithm courses.
The main textbook of the course is
Additional material may be drawn from
Not required but useful references
The full content of the course is described in the course journal. You can look at detailed syllabus for a detailed summary.