Motivation: when computer performance increases, the role of algorithmic efficiency increases as well.

Computational complexity explains why some problems are hard to solve efficiently.

Complexity in life and science: organized vs. disorganized complexity.

Examples: Eulerian cycle (easy) vs. Hamiltonian cycle (presumably hard).
Composite numbers---the existence of a divisor can be detected (relatively) easy, bit finding one is presumably hard.

Turing machine---a mathematical model of computation. An universal Turing machine can simulate any Turing machine given its code ("program").
However, no universal machine can be total: it must loop for some inputs.

An example of a non-computable function: sends a number n to a Turing machine generating n with the minimal number of states.
Intuitively: a shortest program generating n (Kolmogorov complexity).

8 March

Complexity measures: time and space. Complexity of a machine, complexity of a language.
Note: space complexity is defined for the off-line Turing machine.

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

Relation between DTIME and DSPACE. Basic deterministic complexity classes: L, P, PSPACE, EXPTIME.

15 March

Time constructible, and space constructible functions.

Space hierarchy theorem: if S_2 (n) is at least log n, and space constructible, and lim sup S_2(n)/S_1(n) is infinity then there is a language L in DSPACE (S_2(n)) - DSPACE (S_1 (n)).
Proof: adaptation of the diagonal construction for halting problem.

Time hierarchy theorem: analogous, with the assumption that lim sup T_2(n)/T_1(n) log T_2(n) is infinity.

Applications: P and DSPACE (n) are different, by padding argument, although we do not know, which inclusion fails.

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

Boolean circuits (idea)

22 March

Boolean circuits: definition, examples, representation.

A sequence of Boolean circuits as an acceptor of a language.
Parameters: number of variables, depth, size.

Simulation of a (single tape) Turing machine working in time T(n) by a sequence of circuits with T^2 (n) gates and depth T(n).

29 March

Simulation of a sequence of circuits by a machine with advice in time polynomially dependent on the circuits size.

Consequently, P/poly coincides with the class of languages recognized by sequences of circuits of polynomial size.

Similarly, P coincides with the class of languages recognized by uniform sequences of circuits of polynomial size (where uniform means generated in Logspace).

Circuit complexity classes AC^k (polynomial size and depth O ((log n)^k)), and NC^k (as above with the asumption that fan-in of And and Or gates is 2), in both non-uniform and uniform version.
The union of all NC^k classes equals the union of all AC^k classes, and is denoted NC.

Uniform NC is included in P, and uniform NC^1 is included in L, but we don't know if NC^1 is properly included in P.

AC^0 is properly included in NC^1 (information only, without proof).

5 April

Non-determinism. Simulation of a non-deterministic Turing machine by a deterministic one and its cost: NTIME (T(n)) included in DSPACE (T(n)).

Savitch's Theorem: NSPACE (S(n)) included in DSPACE (S(n)^2), for S(n) >= log n.

NL included in P.

Class NP: idea and examples. Decision problems (is there a witness?) vs. search problem (find a witness).

12 April

More on the class NP. Characterization of NP-problems in terms of polynomial relations (as their projections).
Example: Pratt's certificate of primality. Various witnesses that a number is composite.

Polynomial reductions between problems. Example: reduction of 3-SAT to 3-coloring.

26 April

Reductions in the sense of Levin.

NP-completeness of the Boolean Circuit SAT, SAT, CNF-SAT, 3-CNF SAT.

An efficient decision procedure for an NP-complete problem would induce an efficient solution to the search problem.

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

10 May

Alternating Turing machines. Equality AP = PSPACE.

Complete problems in various complexity classes.

Directed reachability in NL.

Alternating reachability and Circuit value in P (w.r.t. Log space reductions).

Alternating circuit satisfiability, QBF, and Universality of non-deterministic automata in PSPACE.

17 May

Immerman-Szelepcsenyi theorem: NSPACE (S(n)) = co-NSPACE (S(n)) (for constructible S(n)>= log n).
In particular, context-sensitive languages are closed under complement (for S(n) = n).
Proof: the problem reduces to non-deterministic computation of the number of reachable configurations.

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

Probabilistic approach to the concept of witness. Positive vs. negative witness, false positives and false negatives.

24 May

Probabilistic complexity classes RP, co-RP, and BPP defined in terms of probabilistic Turing machines or, equivalently, in terms of polynomial relations and random witnesses.

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

Adleman's Theorem: BPP included in P/poly.

31 May

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

Interactive proofs. Example: graph non-isomorphism.

Information about Zero Knoweledge proofs. Example: graph isomorphism.

Shamir's Theorem: IP = PSPACE.
Proof of a weaker statement: an interactive proof for # SAT (computing the number of valuations satisfying a given formula).

7 June

Approximation algorithms.

Examples: 2-approximability of the vertex cover problem, non-approximability of the travelling salesman problem (unless P=NP).

Polynomial approximation scheme for the knapsack problem.

14 June

Information about the PCP theorem and its applications, non-approximability of clique.

Information about FPT algorithms.

Note. The title of the site is borrowed from a song by Tom Paxton.