Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR05-045 | 23rd January 2006 00:00

Martingale Families and Dimension in P

RSS-Feed




Revision #1
Authors: Philippe Moser
Accepted on: 23rd January 2006 00:00
Downloads: 3496
Keywords: 


Abstract:

We introduce a new measure notion on small complexity classes (called F-measure),
based on martingale families,
that gets rid of some drawbacks of
previous measure notions:
it can be used to define dimension because martingale families can make money on all strings,
and it yields random sequences with an equal frequency of 0's and 1's.
As applications to F-measure,
we show that for almost every language A decidable in subexponential time, \p^A =\bpp^A .
We show that almost all languages in \pspace\ do not have small non-uniform complexity.
We compare F-measure to previous notions and prove that martingale families
are strictly stronger than \Gamma-measure, we also discuss
the limitations of martingale families concerning finite unions.
We observe that all classes closed under polynomial many-one reductions have measure zero in \expc\ iff they have
measure zero in \subexp.
We use martingale families to introduce a natural generalization of Lutz resource-bounded dimension
on \p ,
which meets the intuition behind Lutz's notion. We show that \p-dimension lies between finite-state dimension
and dimension on \e.
We prove an analogue to the Theorem of Eggleston in \p ,
i.e. the class of languages whose characteristic sequence contains 1's with frequency \alpha,
has dimension the Shannon entropy of \alpha in \p .


Paper:

TR05-045 | 12th April 2005 00:00

Martingale Families and Dimension in P





TR05-045
Authors: Philippe Moser
Publication: 16th April 2005 03:27
Downloads: 2997
Keywords: 


Abstract:

We introduce a new measure notion on small complexity classes (called F-measure), based on martingale families,
that get rid of some drawbacks of previous measure notions:
martingale families can make money on all strings,
and yield random sequences with an equal frequency of 0's and 1's.
As applications to F-measure,
we answer a question raised in a paper by Allender and Strauss, improving their result to:
for almost every language A decidable in subexponential time,
P^A =BPP^A.
We show that almost all languages in PSPACE require large circuits.
We compare F-measure to previous notions and prove that martingale families are strictly stronger than a previous measure notion on P known
as \Gamma-measure. We also discuss
the limitations of martingale families concerning finite unions.
We observe that all classes closed under polynomial many-one reductions have measure zero in EXP iff they have
measure zero in SUBEXP.
We use martingale families to introduce a natural generalization of Lutz resource-bounded dimension on P,
which meets the intuition behind Lutz's notion.
We show that the class of PSPACE-languages
with small circuit complexity has dimension 0 in PSPACE;
and prove an analogue to
the Theorem of Eggleston in P,
i.e. the class of languages whose characteristic sequence contains 1's with frequency \alpha,
has dimension the Shannon entropy of \alpha in P.



ISSN 1433-8092 | Imprint