ECCC-Report TR05-045https://eccc.weizmann.ac.il/report/2005/045Comments and Revisions published for TR05-045en-usMon, 23 Jan 2006 00:00:00 +0200
Revision 1
| Martingale Families and Dimension in P |
Philippe Moser
https://eccc.weizmann.ac.il/report/2005/045#revision1We 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 .
Mon, 23 Jan 2006 00:00:00 +0200https://eccc.weizmann.ac.il/report/2005/045#revision1
Paper TR05-045
| Martingale Families and Dimension in P |
Philippe Moser
https://eccc.weizmann.ac.il/report/2005/045We 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.
Sat, 16 Apr 2005 03:27:13 +0300https://eccc.weizmann.ac.il/report/2005/045