arnold beckmann
A note on universal measures for weak implicit computational complexity
9th International Conference, LPAR 2002, Tbilisi, Georgia, October 14-18, 2002, Pages: 53 - 67
Publication year: 2002
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.