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: 1343
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: 1170
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