Samuel R. Buss.
"The computational power of bounded arithmetic from the predicative viewpoint"
In: New Computational Paradigms, Changing Conceptions of What is Computable.
Edited by S.B. Cooper, B. Löwe, and A. Sorbi.
Springer, New York, 2008, pp. 213-222.
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.
"The computational power of bounded arithmetic from the
ASL Winter Meeting, New Orleans.
Back to Sam Buss's publications page.