Bounded Arithmetic, Propositional Logic and Complexity Theory

This book presents an up-to-date, unified treatment of research in in this interdisciplinary subject with emphasis on independence proofs and lower bound proofs. A basic introduction is followed by discussion of important results in propositional proof systems and systems of bounded arithmetic. Then more advanced topics are treated, including Boolean complexity, witnessing theorems, and bounded arithmetic as a system of feasible arguments. Students and researchers in logic and computer science will find this an excellent guide to an expanding area.