Measure on P: Robustness of the notion

Eric Allender, Martin Strauss

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations


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

Original languageEnglish (US)
Title of host publicationMathematical Foundations of Computer Science 1995 - 20th International Symposium, MFCS 1995, Proceedings
EditorsJiri Wiedermann, Petr Hajek
PublisherSpringer Verlag
Number of pages10
ISBN (Print)3540602461, 9783540602460
StatePublished - 1995
Event20th International Symposium on Mathematical Foundations of Computer Science, MFCS 1995 - Prague, Czech Republic
Duration: Aug 28 1995Sep 1 1995

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other20th International Symposium on Mathematical Foundations of Computer Science, MFCS 1995
Country/TerritoryCzech Republic

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Measure on P: Robustness of the notion'. Together they form a unique fingerprint.

Cite this