Proof complexity


In theoretical computer science, and specifically 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 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, 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 with two inputs. If P accepts the pair 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 in a propositional interpretation of ZFC is a ZFC-proof of a formalized statement ' 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 is the number of symbols needed to represent the proof. A propositional proof system P is polynomially bounded if there exists a constant such that every tautology of size has a P-proof of size. A central question of proof complexity is to understand if tautologies admit polynomial-size proofs. Formally,
Problem
Does there exist a polynomially bounded propositional proof system?

Cook and Reckhow 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.

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.
For example, sequent calculus is p-equivalent to 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
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 proof system is known to follow from the assumption that NE=coNE.
For many weak proof systems it is known that they do not simulate certain stronger systems. 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
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 proof system P is automatable if there is an algorithm which given a tautology outputs a P-proof of in time polynomial in the size of and the length of the shortest P-proof of. 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 outputs an R-proof of in time polynomial in the size of and the length of the shortest P-proof of.
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,
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 formalizing polynomial-time reasoning and Frege system corresponds to the theory formalizing reasoning.
The correspondence has been introduced by Stephen Cook, who showed that coNP theorems, formally formulas, of the theory 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 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 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.

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. The tautology is true for every choice of, and after fixing the evaluation of and are independent because they are defined on disjoint sets of variables. This means that it is possible to define an interpolant circuit, such that both and hold. The interpolant circuit decides either if is false or if is true, by only considering. The nature of the interpolant circuit can be arbitrary. Nevertheless, it is possible to use a proof of the initial tautology as a hint on how to construct. A proof systems P is said to have feasible interpolation if the interpolant is efficiently computable from any proof of the tautology 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: has a short proof in a some proof system; such proof system has feasible interpolation; the interpolant circuit solves a computationally hard problem. It is clear that and imply that there is a small interpolant circuit, which is in contradiction with. 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. Specifically, many proof systems P are able to prove their own soundness which is a tautology stating that `if is a P-proof of a formula then holds'. Here, are encoded by free variables. Therefore, an efficient interpolant resulting from short P-proofs of soundness of P would decide whether a given formula admits a short P-proof. However, in principle it might be hard to generate such an interpolant if we are provided just a formula. Moreover, 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. On the other hand, weak automatability of a proof system P implies that P admits feasible interpolation.
Many non-automatability results provide actually an evidence against feasible interpolation in the respective systems.
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š 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.