Measure on P: Robustness of the notion

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 є < 1/2) does have measure zero. We also show that our “nonconservative” measure on PSPACE is incomparable with that of [M].