Turing machines and their encodings.

Universal Turing machine U, undecidability of the halting problem.

Non-computable function: the smallest machine generating n.

9 March 2016

Complexity measures: time and space.

Sipser's Theorem: a space bounded Turing machine can be forced to always halt in the same space.

16 March 2016

Basic deterministic complexity classes: L, P, PSPACE, EXPTIME.

Space hierarchy theorem with proof, Time hierarchy theorem (statement). Applications.

23 March 2016

Non-uniform complexity, Turing machine with advice, class P/poly.

Boolean circuits. Simulation of a machine by a sequence of circuits.

Simulation of a sequence of circuits by a machine with advice.

30 March 2016

Non-deterministic space complexity.

Savitch theorem: NSPACE (S(n)) can be simulated by DSPACE (S(n)^2).

Immerman-Szelepcsenyi theorem: NSPACE (S(n)) = co-NSPACE (S(n)).
In particular, context-sensitive languages are closed under complement (for S(n) = n).

6 April 2016

The class NP -- in terms of witnesses and polynomial relations.

Example: Pratt's certificate of primality. Various witnesses that a number is composite.

The class NP -- in terms of non-deterministic Turing machines.

13 April 2016

Reduction between problems in the sense of Turing, Karp, Levin.

Example: reduction of 3-CNF SAT to 3-coloring.

NP-completeness of the Boolean Circuit SAT.

20 April 2016

NP-completeness of SAT, CNF-SAT, 3-CNF SAT

Berman's theorem: a problem over 1 letter alphabet cannot be NP-hard unless P=NP

27 April 2016

Logarithmic reductions. Complete problem in P w.r.t. logarithmic reductions: Circuit value.

Complete problem in NL: directed reachability.

Alternating Turing machines.

Alternating complexity classes in relation to deterministic ones: AL = P, AP = PSPACE.

4 May 2016

Characterization of PSPACE in terms of polynomial relations and game quantifiers.

Complete problems in PSPACE: Quantified Circuit Value, Quantified Boolean Formulae,
Universality of finite non-deterministic automaton.

L-uniform NC1 is included in L.

18 May 2016

Example of a probabilistic algorithm: bipartite matching reduced to computing determinant.

Probabilistic complexity classes RP, co-RP, and BPP defined in terms of probabilistic Turing machines
and, equivalently, in terms of the probability to find a correct witness in polynomial relations.

Reducing the error probability by repeating an algorithm and taking the more frequent answer (calculation).

25 May 2016

Las Vegas algorithms: randomized polynomial time. Characterization in terms of RP intersected with co-RP.

Adleman Theorem: BPP included in P/poly.

Derandomization of probabilistic algorithms by using cryptographically strong pseudo-random generators (idea).

Interactive proofs: example of a proof of graph non-isomorphism.

1 June 2016

Interactive proofs: definition in terms of a probabilistic Turing machine interacting with a strategy.
The class IP of problems recognizable by polynomial time interactive proofs.

Shamir theorem: IP = PSPACE.
Proof of the easier direction: IP included in PSPACE. For the converse, it is enough to show an IP for QBF.
We have showed an IP for #SAT (the number of valuations satisfying a propositional formula).

8 June 2016

Approximation algorithms.

Examples: 2-approximability of the vertex cover problem,
non-approximability of the travelling salesman problem,
polynomial approximation scheme for the knapsack problem.

PCP theorem and non-approximability of clique (very sketchy).