Martingale Families and Dimension in P
2008
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 moneyon all strings, and it yields random sequences with an equal frequency of 0's and 1's. As applications to F-measure, we answer a question raised in [1] by improving their result to:for almost every language A decidable in subexponential time, PA = BPPA. We show thatalmost 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 strongerthan \\Gamma-measure [1], we also discuss the limitations of martingale families concerning finite unions. We observe that all classes closed under polynomial many-one reductions havemeasure zero in EXP iff they have measure zero in SUBEXP. We use martingale familiesto introduce a natural generalization of Lutz resource-bounded dimension [13] on P, whichmeets 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 Egglestonin P, i.e. the class of languages whose characteristic sequence contains 1's with frequency ff, has dimension the Shannon entropy of ff in P.