In (Allender and Strauss, FOCS '95), we defined a notion of measure on the complexity class P (in the spirit of the work of (Lutz, JCSS '92) that provides a notion of measure on complexity classes at least as large as E, and the work of (Mayordomo, Phd. Thesis, 1995) ... more >>>

We consider separations of reducibilities in the context of resource-bounded measure theory. First, we show a result on polynomial-time bounded reducibilities: for every p-random set R, there is a set which is reducible to R with k+1 non-adaptive queries, but is not reducible to any other p-random set with at ... more >>>

We use recent results on the hardness of resource-bounded Kolmogorov random strings, to prove that RP is small in SUBEXP else ZPP=PSPACE and NP=EXP. We also prove that if NP is not small in SUBEXP, then NP=AM, improving a former result which held for the measure on E. more >>>

In this paper, we use resource-bounded dimension theory to investigate polynomial size circuits. We show that for every $i\geq 0$, $\Ppoly$ has $i$th order scaled $\pthree$-strong dimension $0$. We also show that $\Ppoly^\io$ has $\pthree$-dimension $1/2$, $\pthree$-strong dimension $1$. Our results improve previous measure results of Lutz (1992) and dimension ... more >>>

We constructively prove the existence of almost complete problems under logspace manyone reduction for some small complexity classes by exhibiting a parametrizable construction which yields, when appropriately setting the parameters, an almost complete problem for PSPACE, the class of space efficiently decidable problems, and for SUBEXP, the class of problems ... more >>>

We 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, ... more >>>

Under the assumption that NP does not have p-measure 0, we investigate reductions to NP-complete sets and prove the following: - Adaptive reductions are more powerful than nonadaptive reductions: there is a problem that is Turing-complete for NP but not truth-table-complete. - Strong nondeterministic reductions are more powerful than deterministic ... more >>>

This paper investigates the existence of inseparable disjoint pairs of NP languages and related strong hypotheses in computational complexity. Our main theorem says that, if NP does not have measure 0 in EXP, then there exist disjoint pairs of NP languages that are P-inseparable, in fact TIME(2^(n^k)-inseparable. We also relate ... more >>>