Propositional and Algebraic Proof Complexity


We shall survey the most basic concepts of propositional and algebraic
proof complexity: (Cook-Reckhow) Proof systems, optimal proof systems,
coNP=NP iff optimal proof system exists.
   Then we shall turn to algebraic proofs systems, i.e. proofs
manipulating polynomials instead of Boolean formulas: Hilbert's
Nullstellensatz, Polynomial Calculus and Polynomial Calculus with
Resolution. The most studied complexity measure for these systems
 is the maximal degree appearing in a proof.
   Finally we shall consider algebraic proof systems manipulating
arithmetic formulas and circuits for which complexity is measured by
arithmetic size instead of polynomial degree.