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.
Back to Sam Buss's publications page.