Logical Approaches to Computational Barriers

Martingale Families and Dimension in P

Speaker:
| Philippe Moser |

Slot: |
Array, 10:50-11:10, col. 1 |

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 |