Arnold Beckmann
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.

Leave a Reply

Your email address will not be published. Required fields are marked *