In
computer science,
proof complexity is a measure of efficiency of
automated theorem proving methods that is based on the size of the proofs they produce. The methods for proving contradiction in
propositional logic are the most analyzed. The two main issues considered in proof complexity are whether a proof method can produce a polynomial proof of every inconsistent formula, and whether the proofs produced by one method are always of size similar to those produced by another method.