Logical Foundations of Proof Complexity

Cambridge University Press publishes this book, which handles bounded arithmetic and propositional proof complexity through computational complexity theory. Its first seven chapters supply the logical background needed for the rest, and they are written so that they can serve a graduate course.

For each of many complexity classes, the authors pair a two-sorted predicate calculus theory, in which induction is restricted to concepts in that class, with a propositional proof system. The result is a unified framework linking the theories with the proof systems.

Published by Cambridge University Press. ISBN-13: 9780521517294.