__Preprint:__

** Samuel R. Buss.
"The computational power of bounded arithmetic from the
predicative viewpoint"
In: **

** Download: postscript or
PDF.
**

** Abstract: **This paper considers theories of
bounded arithmetic which are predicative in the sense of Nelson, that is,
theories which are interpretable in Robinson's Q . We give a nearly exact
characterization of functions which can be total in predicative bounded
theories. As an upper bound, any such function has polynomial growth rate and
its bit-graph is in nondeterministic exponential time and in
co-nondeterministic exponential time. In fact, any function uniquely defined in
a bounded theory of arithmetic lies in this class. Conversely, any function
which is in this class (provably in I?_{0} + *exp* can be
uniquely defined and total in a (predicative) bounded theory of arithmetic.

__Talk slides:__

**"The computational power of bounded arithmetic from the
predicative viewpoint"
ASL Winter Meeting, New Orleans.
January 2007.**

** Download: ****PDF. **

**Back to Sam Buss's publications page.**