Computability in Europe 2006
Logical Approaches to Computational Barriers


Regular Talk:
Martingale Families and Dimension in P


Speaker: Philippe Moser
Slot: Array, 10:50-11:10, col. 1

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
\cite{Lutz: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 . 


websites: Arnold Beckmann 2006-04-19