TY - GEN

T1 - Measure on P

T2 - 20th International Symposium on Mathematical Foundations of Computer Science, MFCS 1995

AU - Allender, Eric

AU - Strauss, Martin

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1995.

PY - 1995

Y1 - 1995

N2 - 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].

AB - 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].

UR - http://www.scopus.com/inward/record.url?scp=84947914509&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84947914509&partnerID=8YFLogxK

U2 - 10.1007/3-540-60246-1_119

DO - 10.1007/3-540-60246-1_119

M3 - Conference contribution

AN - SCOPUS:84947914509

SN - 3540602461

SN - 9783540602460

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 129

EP - 138

BT - Mathematical Foundations of Computer Science 1995 - 20th International Symposium, MFCS 1995, Proceedings

A2 - Wiedermann, Jiri

A2 - Hajek, Petr

PB - Springer Verlag

Y2 - 28 August 1995 through 1 September 1995

ER -