出版社：The Editorial Committee of the Interdisciplinary Information Sciences
摘要：Proof complexity, a measure to estimate the sizes of proofs in propositional logics, is studied as one of the fundamental approaches to the \mathcal{P} versus \mathcal{NP} problem, and has some practical applications such as automated theorem proving. It is a very hard task to prove lower bounds on strong proof systems such as Frege systems, for which no non-trivial lower bound is known yet. On the other hand, we have some rich success stories on weaker proof systems such as resolution proof systems. In this paper, we focus on resolution proof systems and review some of the existing techniques for proving lower bounds.
