Syllabus for P. Pudlak's lectures at the
Fall school(Sept.'01)

Recent topics in propositional proof complexity
and bounded arithmetic, Part 1.



Lectures 1. and 2.
Complexity theory preliminaries.

Three facets of the same problem (complexity classes, proof systems, first order theories).
P versus NP \cap coNP, Polynomial Hierarchy.
The fourth facet -- disjoint pairs of NP sets (examples, reducibility, polynomial separability, separability by a set in NP\cap coNP, by disjoint coNP sets).
Relevant concepts from cryptography (bit commitment, one way function, pseudorandom generator).
Approximation of the circuit size and the corresponding pair.
Proof systems for propositional calculus (examples, polynomial simulations, the Razborov pair of the system).


Lecture 3. and 4.
Properties of proof systems.

Frege and Substitution rules in general systems.
Feasible interpolation.
Reflection Principle.
Automatizability, essential nonautomatizability.
Unprovability of lower bounds on the circuit size.
Degrees of proof systems and degrees of NP-pairs.