Turing machines and their encodings.

Universal Turing machine U, undecidability of the halting problem.

Non-computable function: the shortest program generating n.

25 February

Turing-Post Theorem: if a set and its complement are partially computable then they are totally computable.

Application: the set Total of encodings of the always-halting Turing machines and its complement are not even partially computable.

Basic complexity measures: time and space.

4 March

Sipser's Theorem: a Turing machine M working in space S(n) can transformed to a machine M' working in the same space,
which moreover always halts. Idea: backtraking.

Basic (deterministic) complexity classes: L, P, PSPACE, EXPTIME. Relation between time and space.

11 March

Space Hierarchy Theorem. If a function S2 (n) grows faster than a function S1 (n) then there is a language in DSPACE ( S2 (n)) and not in DSPACE (S1 (n)).
Here we also assume that S2 (n) is space constructible and at leat log (n).

Corollary: P =/= DSPACE (n), although no inclusion is apriori excluded.

18 March

Boolean circuits -- a model of parallel computation. The depth of the circuits corresponds to the computation time.

Correspondence between Turing machines and circuits. Simulation in both directions.

Non-uniform complexity class P/poly. Its uniform version corresponds precisely to P.

25 March

Problems defined in terms of witnesses. Examples, including short certificates of primality. The existence of witness vs. finding of witness.

The class NP. Two definitions: projection of a polynomial relation, and a polynomial-time non-deterministic Turing machine.

Generalization of non-determinism: alternation (brief information).

1 April

Non-deterministic space-bounded computations.

Let S(n) be fully space-constructible, and at least log (n). Then

Savitch's Theorem: NSPACE (S(n)) included in DSPACE (S(n)^2), consequently NPSPACE = PSPACE.

Immerman-Szelepcsenyi Theorem: NSPACE (S(n)) = co-NSPACE (S(n))
(proof next week).

8 April

Reduction between problems. Case study: breaking the last bit in RSA would break the whole system.

Basic concepts: Turing-Cook reduction, Karp reduction, Levin reduction.

15 April

NP-completeness w.r.t. Karp/Levin reductions. Circuit-SAT, SAT, 3-CNF SAT, 3-Coloring.

Having an algorithm, which solves a problem existentially, can we always find a witness? It works for NP-complete problems, but presumably not in general.

29 April

Optimization problems: shortest path, maximal clique, minimal number of colors.

Pseudo-polynomial algorithm for knapsack problem.

Polynomial-time approximation algorithms. Positive example: minimal vertex cover. Negative example: travelling salesman problem (fails unless P=NP).

Polynomial time approximation scheme for knapsack problem.

6 May

Problems complete under logarithmic reduction: Circuit Value in P, directed reachability in NL.

Alternating Turing machines, AP = PSPACE. Characterization of PSPACE by game quantifier. Problem complete in PSPACE: quantified circuit satisfiability.

13 May

Randomized algorithms. Examples: perfect matching, equality of polynomials.

Definition of probabilistic complexity classes: BPP and RP in term of witnesses.

Improving certainty by majority voting, amplification of constants.

Derandomization: BPP included in P/poly.

Probabilistic Turing machines.

20 May

Interactive proofs. Examples: graph non-isomorphism, fast evaluation of arithmetic expressions.

IP extends both NP, co-NP, and BPP.