This class is an introduction to the wonderful world of Computational Complexity. Computational Complexity studies the intrinsic complexity of computational problems and constitutes the mathematical core of Computer Science. Since I have very limited time I decided to concentrate on a few topics chosen on the basis of my very personal taste.
Lectures
Lecture 1.
The class P as the class of languages that can be efficiently decided.
The class NP as the class of languages that can be efficiently
verified and as class of langages accepted by a non-deterministic
Turing machine in poly time. Equivalence of the two definitions.
Self reducible languages: SAT and Grap Isomorphism.
Lecture 2.
Cook and Karp reductions. Bounded Halting is NP-complete. Circuit Sat is
NP-complete. All NP-complete languages are self-reducible.
Homework 1 available here
with some solutions.
The following students have submitted solutions: P. Ambrosio,
G. Raimato, A. Castiglione, G. Graziano, C. Ventre, A. Sala,
F. Sorrentino, A. Nappi, C. Soriente.
Come and talk to me about your homework if you want.
Lecture 3.
Probabilistic computation classes.
RP and co-RP. RP is in NP. BPP and probability amplification.
PP. PP contains NP. ZPP and ZP is equal to the intersection of
RP and co-RP.
Lecture 4.
P/poly via Turing machines with poly-size advice and as
non-uniform poly-size circuits. P/poly contains non-recursive languages.
BPP is included in P/poly. NP is in P/poly iff SAT is Cook-reducible to
a sparse language.
The Polynomial Hierarchy defined using quantifiers and using oracles.
BPP is included in Sigma2.
Lecture 5.
IP and Arthur-Merlin Games. Graph NonIso in IP(2).
IP=PSPACE. IP=IP with perfect completeness.
Lecture 6.
Pseudo-random generator. Stretching by one bit is enough.
Hard-core bit and one-way permutations. Construction based
on one-way permutations. Derandomizing BPP.
Homework 2 with solutions available here.
Documents
Links to other complexity sites