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)
In building E, in Viale Regina Elena, 295.
The course starts on September 19th, and goes on for 24 lectures up until, roughly, December 22nd. 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 actual program of the course will develop during the semester.