__Book article:__

** Samuel R. Buss.
"Bounded Arithmetic"
Bibliopolis, Naples, Italy, 1986.
Revision of 1985 Ph.D. Thesis (Department of Mathematics,
Princeton University).**

** Download entire book: Searchable
PDF (6MB) or plain PDF (2 MB). **

** Table of contents: **.

- Introduction.
- The polynomial hierarchy.
- Foundations of bounded arithmetic
- Definability of polynomial hierarchy functions.
- First-order natural deduction systems.
- Computational complexity of definable functions
- Cook's equational theory PV.
- Godel incompleteness theorems.
- A proof-theoretic statement equivalent to NP=coNP.
- Foundations of second order bounded arithmetic.
- Definable functions of second-order bounded arithmetic.
- Postscript
- References.
- Symbol index.
- Subject index.