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: .

  1. Introduction.
  2. The polynomial hierarchy.
  3. Foundations of bounded arithmetic
  4. Definability of polynomial hierarchy functions.
  5. First-order natural deduction systems.
  6. Computational complexity of definable functions
  7. Cook's equational theory PV.
  8. Godel incompleteness theorems.
  9. A proof-theoretic statement equivalent to NP=coNP.
  10. Foundations of second order bounded arithmetic.
  11. Definable functions of second-order bounded arithmetic.
  12. Postscript
  13. References.
  14. Symbol index.
  15. Subject index.

 Back to Sam Buss's publications page.