We are interested in studying the length of the shortest proof of a propositional tautology in
various proof systems as a function of the length of the tautology. The smallest upper bound …

We prove that, for infinitely many disjunctive normal form propositional calculus tautologies
ξ, the length of the shortest resolution proof of ξ cannot be bounded by any polynomial of the …

Two decidable logical theories are presented, one complete for deterministic polynomial
time, one complete for polynomial space. Both have natural proof systems. A lower space …

This dissertation discusses first and second order theories of Bounded Arithmetic and
relates the definability of functions in these theories to computational complexity. The types …

The purpose of this book is to organize, augment when necessary, and record the major
conceptual advances in an aspect of automated theorem proving that peaked during the …

Since both the coments and the structure of the book appeared to be successful, only minor
changes were made. In particular, some recent work in ATP has been incorporated so that …

It is the purpose of this note to show that the question of whether a given propositional
formula is intuitionistically valid (in Brouwer's sense, in Kripke's sense, or just provable by …

This account of propositional logic concentrates on the algorithmic translation of important
methods, especially of decision procedures for (subclasses of) propositional logic. Important …

§ 1. Introduction. The classical propositional calculus has an undeserved reputation among
logicians as being essentially trivial. I hope to convince the reader that it presents some of …

The motivation for this work comes from two general sources. The first source is the basic
open question in complexity theory of whether P equals NP (see [Coo71b] and [Kar72]). Our …