arnold beckmann's pages

A note on universal measures for weak implicit computational complexity

File: PDF-File

Author: Arnold Beckmann
Title: A note on universal measures for weak implicit computational complexity
Proceedings: 9th International Conference, LPAR 2002, Tbilisi, Georgia, October 14-18, 2002
Pages: 53 - 67
DOI: 10.1007/3-540-36078-6_4

Abstract: This note is a case study for finding universal measures for weak implicit complexity. We will instanciate "universal measures" by "dynamic ordinals", and "weak implicit complexity" by "bounded arithmetic". Concretely, we will describe the connection between dynamic ordinals and witness oracle Turing machines for bounded arithmetic theories.

websites: Arnold Beckmann 2017-08-28 Valid HTML 4.01! Valid CSS!