Proof complexity

In logic and theoretical computer science, and specifically proof theory and computational complexity theory, proof complexity is the field aiming to understand and analyse the computational resources that are required to prove or refute statements. Research in proof complexity is predominantly concerned with proving proof-length lower and upper bounds in various propositional proof systems. For example, among the major challenges of proof complexity is showing that Frege system, the usual propositional calculus, does not admit polynomial-size proofs of all tautologies; here the size of the proof is simply the number of symbols in it, and a proof is said to be of polynomial size if it is polynomial in the size of the tautology it proves.
Systematic study of proof complexity began with the work of Stephen Cook and Robert Reckhow (1979) who provided the basic definition of a propositional proof system from the perspective of computational complexity. Specifically Cook and Reckhow observed that proving proof size lower bounds on stronger and stronger propositional proof systems can be viewed as a step towards separating NP from coNP (and thus P from NP), since the existence of a propositional proof system that admits polynomial size proofs for all tautologies is equivalent to NP=coNP.
Contemporary proof complexity research draws ideas and methods from many areas in computational complexity, algorithms and mathematics. Since many important algorithms and algorithmic techniques can be cast as proof search algorithms for certain proof systems, proving lower bounds on proof sizes in these systems implies run time lower bounds on the corresponding algorithms. This connects proof complexity to more applied areas such as SAT solving.
Mathematical logic can also serve as a framework to study propositional proof sizes. First-order theories and, in particular, weak fragments of Peano Arithmetic, which come under the name Bounded Arithmetic theories, serve as uniform versions of propositional proof systems and provide further background for interpreting short propositional proofs in terms of various levels of feasible reasoning.
Proof systems.
A propositional proof system is given as a proof-verification algorithm "P"("A","x") with two inputs. If "P" accepts the pair ("A","x") we say that "x" is a "P"-proof of "A". "P" is required to run in polynomial time, and moreover, it must hold that "A" has a "P"-proof if and only if it is a tautology.
Examples of propositional proof systems include Sequent calculus, Resolution, Cutting Planes and Frege system. Strong mathematical theories such as ZFC induce propositional proof systems as well: a proof of a tautology formula_1 in a propositional interpretation of ZFC is a ZFC-proof of a formalized statement 'formula_1 is a tautology'.
Proofs of polynomial size and the NP versus coNP problem.
Proof complexity measures the efficiency of the proof system usually in terms of the minimal size of proofs possible in the system for a given tautology. The size of a proof (resp. formula) is the number of symbols needed to represent the proof (resp. formula). A propositional proof system "P" is "polynomially bounded" if there exists a constant formula_3 such that every tautology of size formula_4 has a "P"-proof of size formula_5. A central question of proof complexity is to understand if tautologies admit polynomial-size proofs. Formally,
Problem (NP vs. coNP) 
Does there exist a polynomially bounded propositional proof system?
Cook and Reckhow (1979) observed that there exists a polynomially bounded proof system if and only if NP=coNP. Therefore, proving that specific proof systems do not admit polynomial size proofs can be seen as a partial progress towards separating NP and coNP (and thus P and NP).
Optimality and simulations between proof systems.
Proof complexity compares the strength of proof systems using the notion of simulation. A proof system "P" "p-simulates" a proof system "Q" if there is a polynomial-time function which given a "Q"-proof outputs a "P"-proof of the same tautology. If "P" p-simulates "Q" and "Q" p-simulates "P", the proof systems "P" and "Q" are "p-equivalent". There is also a weaker notion of simulation: a proof system "P" "simulates" a proof system "Q" if there is a polynomial "p" such that for every "Q"-proof "x" of a tautology "A", there is a "P"-proof "y" of "A" such that the length of "y", |"y"| is at most "p"(|"x"|).
For example, sequent calculus is p-equivalent to (every) Frege system.
A proof system is "p-optimal" if it "p"-simulates all other proof systems, and it is "optimal" if it simulates all other proof systems. It is an open problem whether such proof systems exist:
Problem (Optimality) 
Does there exist a p-optimal or optimal propositional proof system?
Every propositional proof system "P" can be simulated by Extended Frege extended with axioms postulating soundness of "P". The existence of optimal (resp. p-optimal) proof system is known to follow from the assumption that NE=coNE (resp. E=NE).
For many weak proof systems it is known that they do not simulate certain stronger systems (see below). However, the question remains open if the notion of simulation is relaxed. For example, it is open whether Resolution "effectively polynomially simulates" Extended Frege.
Automatability of proof search.
An important question in proof complexity is to understand the complexity of searching for proofs in proof systems.
Problem (Automatability) 
Are there efficient algorithms searching for proofs in standard proof systems such as Resolution or Frege system? 
The question can be formalized by the notion of automatability (a.k.a. automatizability).
A proof system "P" is "automatable" if there is an algorithm which given a tautology formula_1 outputs a "P"-proof of formula_1 in time polynomial in the size of formula_1 and the length of the shortest "P"-proof of formula_1. Note that if a proof system is not polynomially bounded, it can still be automatable. A proof system "P" is "weakly automatable" if there is a proof system "R" and an algorithm which given a tautology formula_1 outputs an "R"-proof of formula_1 in time polynomial in the size of formula_1 and the length of the shortest "P"-proof of formula_1.
Many proof systems of interest are believed to be non-automatable. However, currently only conditional negative results are known.
It is not known if the weak automatability of Resolution would break any standard complexity-theoretic hardness assumptions.
On the positive side,
Bounded arithmetic.
Propositional proof systems can be interpreted as nonuniform equivalents of theories of higher order. The equivalence is most often studied in the context of theories of bounded arithmetic. For example, Extended Frege system corresponds to Cook's theory formula_15 formalizing polynomial-time reasoning and Frege system corresponds to the theory formula_16 formalizing formula_17 reasoning.
The correspondence has been introduced by Stephen Cook (1975), who showed that coNP theorems, formally formula_18 formulas, of the theory formula_15 translate to sequences of tautologies with polynomial-size proofs in Extended Frege. Moreover, Extended Frege is the weakest such system: if another proof system "P" has this property, then "P" simulates Extended Frege.
An alternative translation between second-order statements and propositional formulas given by Jeff Paris and Alex Wilkie (1985) has been more practical for capturing subsystems of Extended Frege such as Frege or constant-depth Frege.
While the above mentioned correspondence says that proofs in a theory translate to sequences of short proofs in the corresponding proof system, a form of the opposite implication holds as well. It is possible to derive lower bounds on size of proofs in a proof system "P" by constructing suitable models of a theory "T" corresponding to the system "P". This allows to prove complexity lower bounds via model-theoretic constructions, an approach known as Ajtai's method.
SAT solvers.
Propositional proof systems can be interpreted as nondeterministic algorithms for recognizing tautologies. Proving a superpolynomial lower bound on a proof system "P" thus rules out the existence of a polynomial-time algorithm for SAT based on "P". For example, runs of DPLL algorithm on unsatisfiable instances correspond to tree-like Resolution refutations. Therefore, exponential lower bounds for tree-like Resolution (see below) rule out the existence of efficient DPLL algorithms for SAT. Similarly, exponential Resolution lower bounds imply that SAT solvers based on Resolution, such as CDCL algorithms cannot solve SAT efficiently (in worst-case).
Lower bounds.
Proving lower bounds on lengths of propositional proofs is generally very difficult. Nevertheless, several methods for proving lower bounds for weak proof systems have been discovered.
It is a long-standing open problem to derive a nontrivial lower bound for Frege system.
Feasible interpolation.
Consider a tautology of the form formula_20. The tautology is true for every choice of formula_21, and after fixing formula_21 the evaluation of formula_23 and formula_24 are independent because they are defined on disjoint sets of variables. This means that it is possible to define an "interpolant" circuit formula_25, such that both formula_26 and formula_27 hold. The interpolant circuit decides either if formula_28 is false or if formula_29 is true, by only considering formula_21. The nature of the interpolant circuit can be arbitrary. Nevertheless, it is possible to use a proof of the initial tautology formula_20 as a hint on how to construct formula_32. A proof systems "P" is said to have "feasible interpolation" if the interpolant formula_25 is efficiently computable from any proof of the tautology formula_34 in "P". The efficiency is measured with respect to the length of the proof: it is easier to compute interpolants for longer proofs, so this property seems to be anti-monotone in the strength of the proof system.
The following three statements cannot be simultaneously true: (a) formula_34 has a short proof in a some proof system; (b) such proof system has feasible interpolation; (c) the interpolant circuit solves a computationally hard problem. It is clear that (a) and (b) imply that there is a small interpolant circuit, which is in contradiction with (c). Such relation allows to turn proof length upper bounds into lower bounds on computations, and dually to turn efficient interpolation algorithms into lower bounds on proof length.
Some proof systems such as Resolution and Cutting Planes admit feasible interpolation or its variants.
Feasible interpolation can be seen as a weak form of automatability. In fact, for many proof systems, such as Extended Frege, feasible interpolation is equivalent to weak automatability. Specifically, many proof systems "P" are able to prove their own soundness which is a tautology formula_36 stating that `if formula_37 is a "P"-proof of a formula formula_38 then formula_38 holds'. Here, formula_40 are encoded by free variables. Moreover, it is possible to generate "P"-proofs of formula_36 in polynomial-time given the length of formula_37 and formula_43. Therefore, an efficient interpolant resulting from short "P"-proofs of soundness of "P" would decide whether a given formula formula_43 admits a short "P"-proof formula_37. Such an interpolant can be used to define a proof system "R" witnessing that "P" is weakly automatable. On the other hand, weak automatability of a proof system "P" implies that "P" admits feasible interpolation. However, if a proof system "P" does not prove efficiently its own soundness, then it might not be weakly automatable even if it admits feasible interpolation.
Many non-automatability results provide actually an evidence against feasible interpolation in the respective systems.
Non-classical logics.
The idea of comparing the size of proofs can be used for any automated reasoning procedure that generates a proof. Some research has been done about the size of proofs for propositional non-classical logics, in particular, intuitionistic, modal, and non-monotonic logics.
Hrubeš (2007-2009) proved exponential lower bounds on size of proofs in Extended Frege system in some modal logics and intuitionistic logic using a version of monotone feasible interpolation.