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. On larger complexity classes (
![View the MathML source View the MathML source](http://www.sciencedirect.com/cache/MiamiImageURL/B6V1G-4RVG3RW-2-V/0?wchp=dGLbVlz-zSkWb)
and above),
F-measure is equivalent to Lutz resource-bounded measure. As applications to
F-measure, we answer a question raised in [E. Allender, M. Strauss, Measure on small complexity classes, with application for BPP, in: Proc. of the 35th Ann. IEEE Symp. on Found. of Comp. Sci., 1994, pp. 807–818] by improving their result to: for almost every language
A decidable in subexponential time,
![View the MathML source View the MathML source](http://www.sciencedirect.com/cache/MiamiImageURL/B6V1G-4RVG3RW-2-10/0?wchp=dGLbVlz-zSkWb)
. We show that almost all languages in
![View the MathML source View the MathML source](http://www.sciencedirect.com/cache/MiamiImageURL/B6V1G-4RVG3RW-2-B/0?wchp=dGLbVlz-zSkWb)
do not have small non-uniform complexity. We compare
F-measure to previous notions and prove that martingale families are strictly stronger than
Γ-measure [E. Allender, M. Strauss, Measure on small complexity classes, with application for BPP, in: Proc. of the 35th Ann. IEEE Symp. on Found. of Comp. Sci., 1994, pp. 807–818], 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
![View the MathML source View the MathML source](http://www.sciencedirect.com/cache/MiamiImageURL/B6V1G-4RVG3RW-2-W/0?wchp=dGLbVlz-zSkWb)
iff they have measure zero in
![View the MathML source View the MathML source](http://www.sciencedirect.com/cache/MiamiImageURL/B6V1G-4RVG3RW-2-S/0?wchp=dGLbVlz-zSkWb)
. We use martingale families to introduce a natural generalization of Lutz resource-bounded dimension [J.H. Lutz, Dimension in complexity classes, in: Proceedings of the 15th Annual IEEE Conference on Computational Complexity, 2000, pp. 158–169] on
![View the MathML source View the MathML source](http://www.sciencedirect.com/cache/MiamiImageURL/B6V1G-4RVG3RW-2-D/0?wchp=dGLbVlz-zSkWb)
, which meets the intuition behind Lutz’s notion. We show that
![View the MathML source View the MathML source](http://www.sciencedirect.com/cache/MiamiImageURL/B6V1G-4RVG3RW-2-H/0?wchp=dGLbVlz-zSkWb)
-dimension lies between finite-state dimension and dimension on
![View the MathML source View the MathML source](http://www.sciencedirect.com/cache/MiamiImageURL/B6V1G-4RVG3RW-2-P/0?wchp=dGLbVlz-zSkWb)
. We prove an analogue of a Theorem of Eggleston in
![View the MathML source View the MathML source](http://www.sciencedirect.com/cache/MiamiImageURL/B6V1G-4RVG3RW-2-K/0?wchp=dGLbVlz-zSkWb)
, i.e. the class of languages whose characteristic sequence contains
1’s with frequency
a559859edf6e" title="Click to view the MathML source" alt="Click to view the MathML source">![greek small letter alpha greek small letter alpha](http://www.sciencedirect.com/scidirimg/entities/204e.gif)
, has dimension the Shannon entropy of
1a52" title="Click to view the MathML source" alt="Click to view the MathML source">![greek small letter alpha greek small letter alpha](http://www.sciencedirect.com/scidirimg/entities/204e.gif)
in
![View the MathML source View the MathML source](http://www.sciencedirect.com/cache/MiamiImageURL/B6V1G-4RVG3RW-2-G/0?wchp=dGLbVlz-zSkWb)
.