Course program
1. Basic on Complexity Classes [2 weeks]
1.1 Theoretical models of computations and time and space resources
1.2 Time and space complexity classes
1.3 The P = NP problem
1.4 NP and NP-completeness
1.5 Unfeasible problems when resources are bounded
1.6 Computational Classes: L, NL, P, NP, PSPACE, BPP, RP, #P, IP,
1.7 Main Results
2. Diagonalization [1 week]
3. Hierarchies Theorems for time, space, deterministic and non deterministic computations [1 week]
4. Barriers Results I: Diagonalization is not sufficient to prove P different from NP [1 week]
5. Space Complexity [2 weeks]
5.1 Shamir Theorem: PSPACE = IP
5.2 Immerman-Szelepcsényi Theorem: NL=coNL,
6. Boolean Circuits [2 weeks]
6.1 Basic definitions and efficient circuits
6.2 Bounded depth circuits: NC and AC hierarchies.
6.3 Hastad-Razborov-Smolensky Theorem: Parity requires exponential size bounded depth circuits.
6.4 Monotone Circuits
7. Polynomial Hierarchy and its basic theorems [1 week]
8. Barriers Results - II [1 week, optional, if time allows]
8.1 Rudich-Razborov Theorem: "Natural proofs" are not sufficient to separate P from NP (unless crypto fails)
9. Other boolean models of computations and their limit: [1 week]
9.1 Decision trees
9.2 Branching programs.
10. Introduction to Proof Complexity [2 weeks]
10.1. Logical proof systems: Resolution
10.2 Geometric proof systems: Chvatal's cuts
10.3 Algebraic proof system: Polynomial Calculus
10.4 Semialgebraic proof systems: Sherali-Adams and Sum-of-Squares
10.5 Exponential lower bounds for Resolution and Cutting planes: Ben-Sasson-Wigdeson width method and
Interpolation
Prerequisites
Basic notions of discrete mathematics (counting, graphs, permutations, ) [important]
Notion of algorithm and data structure (Stack, queue, trees)[important]
Efficient algorithms exploiting data information (for instance, binary search)[important]
Basic notions of propositional logic [important]
Notion of Relation of generic arity[important]
Notion of universal and existential Quantification[important]
Concetto di Relazione di arità generica[important]
Basic notions of first order Logic[important]
Advanced Notions on Languages [important]
Computational models [important]
Basic Notions of Complexity Theory [importante]
Books
S. Arora B. Barak: Computational Complexity: A Modern Approach Cambridge University Press, 2007
O. Goldreich. P, NP, and NP-Completeness: The Basics of Computational Complexity Cambridge University Press 2010
O. Goldreich. Computational Complexity: A Conceptual Perspective Cambridge University Press 2008.
A. Wigderson. Mathematics and Computation. Princeton University Press. In press
C. Papadimitriou. Computational Complexity. Pearsons. 1994.
S. Jukna. Boolean Function Complexity. Springer. 2012
H. Vollmer. Introduction to Circuit Complexity: an uniform approach, Springer. 2013
J. Krajicek. Proof Complexity. Cambridge. 2019.
Frequency
not mandatory
Exam mode
To pass the exam the student must obtain a final mark that must be greater than or equal to 18/30.
To obtain the minimal mark the student must effectively shown a sufficient knowledge covering
all the topics treated along the lectures and he must be able to connect to each other all the topics covered.
To obtain the full mark of 30/30 e lode it is necessary to show to have reached an outstanding knowledge of all the topics covered in the lectures. Furthermore the student must give proof of evidence to be able to logically connect all the topics.
The following aspects will be considered towards the final evaluation of the exam:
(1) the logic followed by the student for the solution of the problems;
(2) the correctness and the soundness of the solutions of the problems;
(3) how compatible are the solutions to the problems of the exams in accordance to the knowledge and the ability
the student has received along all the lectures.
(4) the ability to write correctly in Italian (or English if the exam is in English)
We will consider also the following aspects:
(1) the ability to elaborate a correct and clear answer to the questions raised and
(2) the readiness of the student in answering the questions
(3) How the student is able to infer genuine new knowledge from the topics covered during the lectures.
Lesson mode
The teaching model used is that of blackboard lectures integrated if possible with the following
(1) lab classes, which includes solution of concrete problems raising form the theory
(2) group works
(3) flipped-classroom when the students receive homework to be presented during the lectures
(4) Oral questions asked to the students during the lectures by the teacher.
Hardware and software (for example Menti Meter) tools will be used if possible to stimulate the learning process of the student and
to make clearer to the student the evolution of his learning process of the topics covered during the lectures.
Materials (slide, communications, videoclasses, problems, solutions etc.) and the management of the course is done weekly on the E-Learning page (Sapienza) of the course that each year is provided by the teacher
