Preprint:

    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.

 

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.