In this paper we prove an exponential lower bound on the size of bounded-depth Frege
proofs for the pigeonhole principle (PHP). We also obtain an Ω (loglog n)-depth lower bound …

A resolution proof of an unsatisfiable propositional formula is called regular if and only if no
variable is eliminated (with the resolution rule) twice on any branch of the proof tree …

This report provides a detailed description of the TPTP Problem Library for automated
theorem proving systems. This library is available via Internet, and is intended to form a …

We introduce new proof systems for propositional logic, simple deduction Frege systems,
general deduction Frege systems, and nested deduction Frege systems, which augment …

The combinatorial matching principle states that there is no perfect matching on an odd
number of vertices. This principle generalizes the pigeonhole principle, which states that for …

Frege systems with the deduction rule produce at most quadratic speedup over Frege
systems using as a measure of length the number of symbols in the proof. We study whether …

This thesis is a study of the relationship between proof systems for propositional logic and
for logics of restricted quantification incorporating restriction theories. Such logics are …

Cut formulas in propositional logic can speed up some proofs exponentially[S](a cut-free
system is used as reference when we talk about speed-ups); it is hence important to study …

The relative complexity of analytic tableaux and SL-resolution Page 1 ANDtt~ VI~I.IANO The
Relative Complexity of Analytic Tableaux and SL-Resolution Abstract. In this paper we describe …

It is known that the minimal number of the steps in a proof of a tautology in a Frege system
can be exponentially larger than in a substitution Frege system, but it is an open problem …