ABSTRACT
Many formal systems admit such kind of universal measures. For exam ple, in case of “strong” implicit computational complexity, e.g. for numbertheoretic functions which are computable by primitive recursive functionals in finite types, so-called proof-theoretic ordinals have proven useful as universal measures of proof and computation (and also consistency) strength (cf. [19]). With respect to our general picture this situation can be represented as follows:
In this paper, we will focus on weak, also called low-level, complexity classes, i.e. complexity classes below EXPTIME. We will approach the general idea of finding universal measures by doing a case study for a particular framework of weak implicit computational complexity called bounded arithmetic. We already argued in [3] that so-called dynamic ordinals can be viewed as univer sal measures for some fragments of bounded arithmetic and corresponding bounded witness oracle Turing machine classes. In this paper, we will ex tend this project by defining and computing generalised dynamic ordinals and indicating their role as universal measures for all bounded arithmetic theories.
