|
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 [M], one obtains strictly more measurable sets if one considers "nonconservative " martingales that succeed merely in the lim sup rather than having a limit of infinity. For example, it is shown in [AS] that the class of sparse sets does not have measure zero in P, whereas here we show that using the "nonconservative " measure, the class of sparse sets (and in fact the class of sets with density ffl! 1=2) does have measure zero. We also show that our "nonconservative " measure on PSPACE is incomparable with that of [M]. 1, |
