Abstract
In [AS], we defined a notion of measure on the complexity class P (in the spirit of the work of Lutz [L92] that provides a notion of measure on complexity classes at least as large as E, and the work of Mayordomo [M] that provides a measure on PSPACE). In this paper, we show that several other ways of defining measure in terms of covers and martingales yield precisely the same notion as in [AS]. (Similar “robustness” results have been obtained previously for the notions of measure defined by [L92] and [M], but — for reasons that will become apparent below — different proofs are required in our setting.)
To our surprise, and in contrast to the measures of Lutz [L92] and Mayordomo.