Logical Foundations of Proof Complexity


Stephen Cook and Phuong Nguyen (c) copyright 2004, 2005, 2006,2007,2008 To be published by the Perspectives in Logic series of the Association for Symbolic Logic through Cambridge University Press.

The current draft (posted September 2, 2008) has 439 pages and is mostly complete except for parts of Chapters 9 and 10 and the Appendix. Further editing is intended.

PLEASE SEND COMMENTS AND CORRECTIONS TO THE AUTHORS

Preface, Table of Contents, Introduction (.ps) (15 pages)

Book (including index) (.ps) (9 + 439 pages)

CHAPTER TITLES:

Introduction
The Predicate Calculus and the System LK
Peano Arithmetic and its Subsystems
Two-Sorted Logic and Complexity Classes
The Theory V0 and AC0
The Theory V1 and Polynomial Time
Propositional Translations
Theories for Polynomial Time and Beyond
Theories for Small Classes
The Reflection Principle
(Appendix) Computational Models