Bounded arithmetic, propositional logic, and complexity theory.

*(English)*Zbl 0835.03025
Encyclopedia of Mathematics and Its Applications. 60. Cambridge: Cambridge Univ. Press. xiv, 341 p. (1995).

The book under review is an up-to-data monograph devoted to bounded arithmetic and complexity of propositional logic with emphasis on independence proofs and lower bound proofs. Connections between logic and complexity theory are discussed.

The book consists of 15 chapters and is supplemented by references and indexes of subjects, names and symbols. It begins with an introduction to the basics of logic and complexity theory. Then results on propositional proof systems and systems of bounded arithmetic are discussed. Furthermore advanced topics are treated, including polynomial simulations and conservativity results, various witnessing theorems, the translation of bounded formulas (and their proofs) into propositional ones, the method of random partial restrictions and its applications, direct independence proofs, complete systems of partial relations, the method of Boolean valuations, combinatorics and complexity theory within bounded arithmetic, and relations to complexity issues of predicate calculus.

The material is presented in a complete and up-to-date way. The book is not intended as a textbook but rather as a presentation of the main aspects of contemporary research in bounded arithmetic and complexity of propositional logic. It can be used by researching mathematicians, computer scientists and graduate students.

The book consists of 15 chapters and is supplemented by references and indexes of subjects, names and symbols. It begins with an introduction to the basics of logic and complexity theory. Then results on propositional proof systems and systems of bounded arithmetic are discussed. Furthermore advanced topics are treated, including polynomial simulations and conservativity results, various witnessing theorems, the translation of bounded formulas (and their proofs) into propositional ones, the method of random partial restrictions and its applications, direct independence proofs, complete systems of partial relations, the method of Boolean valuations, combinatorics and complexity theory within bounded arithmetic, and relations to complexity issues of predicate calculus.

The material is presented in a complete and up-to-date way. The book is not intended as a textbook but rather as a presentation of the main aspects of contemporary research in bounded arithmetic and complexity of propositional logic. It can be used by researching mathematicians, computer scientists and graduate students.

Reviewer: R.Murawski (Poznań)

##### MSC:

03F30 | First-order arithmetic and fragments |

03D15 | Complexity of computation (including implicit computational complexity) |

03-02 | Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations |