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 the usual propositional-calculus does not admit polynomial-size proofs of all tautologies (the actual formalization of a propositional-calculus is immaterial here, since all natural formalizations have been proved to be polynomially-identical); 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. 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 the usual propositional-calculus does not admit polynomial-size proofs of all tautologies (the actual formalization of a propositional-calculus is immaterial here, since all natural formalizations have been proved to be polynomially-identical); 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.