Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR95-028 | 9th June 1995 00:00

Measure on P: Robustness of the Notion


Authors: Eric Allender, Martin Strauss
Publication: 9th June 1995 18:07
Downloads: 1161


In (Allender and Strauss, FOCS '95), we defined a notion of
measure on the complexity class P (in the spirit of the work of (Lutz,
JCSS '92) that provides a notion of measure on complexity classes at least
as large as E, and the work of (Mayordomo, Phd. Thesis, 1995) 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 (Allender and Strauss).
(Similar ``robustness'' results have been obtained previously for
the notions of measure defined by Lutz and Mayordomo, but -- for reasons
that will become apparent below -- different proofs are required in our

To our surprise, and in contrast to the measures of Lutz and Mayordomo,
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 (Allender, Strauss) 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 epsilon < 1/2) does have
measure zero. We also show that our ``nonconservative'' measure on
PSPACE is incomparable with that of Mayordomo.

ISSN 1433-8092 | Imprint