Eric Allender, Martin Strauss

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

Wolfgang Merkle

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

Philippe Moser

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

Xiaoyang Gu

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 >>>

Olivier Powell

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 >>>

Philippe Moser

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 >>>

John Hitchcock, A. Pavan

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

Jack H. Lutz, Elvira Mayordomo

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 >>>

John Hitchcock, Adewale Sekoni

The measure hypothesis is a quantitative strengthening of the P $\neq$ NP conjecture which asserts that NP is a nonnegligible subset of EXP. Cai, Sivakumar, and Strauss (1997) showed that the analogue of this hypothesis in P is false. In particular, they showed that NTIME[$n^{1/11}$] has measure 0 in P. ... more >>>

John Hitchcock, Adewale Sekoni, Hadi Shafei

Bennett and Gill (1981) showed that P^A != NP^A != coNP^A for a random

oracle A, with probability 1. We investigate whether this result

extends to individual polynomial-time random oracles. We consider two

notions of random oracles: p-random oracles in the sense of

martingales and resource-bounded measure (Lutz, 1992; Ambos-Spies ...
more >>>