期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1995
卷号：1995
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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
setting.)
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.
