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 …

Since their inception, the Perspectives in Logic and Lecture Notes in Logic series have
published seminal works by leading logicians. Many of the original books in the series have …

Nonstandard models of arithmetic are of interest to mathematicians through the presence of
infinite (or nonstandard) integers and the various properties they inherit from the finite …

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 …

We give a recursion-theoretic characterization of FP which describes polynomial time
computation independently of any externally imposed resource bounds. In particular, this …

This book presents an up-to-date, unified treatment of research in bounded arithmetic and
complexity of propositional logic with emphasis on independence proofs and lower bound …

This chapter gives an overview of proof complexity and connections to SAT solving, focusing
on proof systems such as resolution, Nullstellensatz, polynomial calculus, and cutting planes …

As introduced by Chvátal, cutting planes provide a canonical way of proving that every
integral solution of a given system of linear inequalities satisfies another specified inequality …

Usual typed lambda-calculi yield input/output specifications; in this paper the authors show
how to extend this paradigm to complexity specifications. This is achieved by means of a …

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 …