**Abstract**:

Juedes and Lutz (1995)
proved a small span theorem for polynomial-time
many-one reductions in exponential time. This result says that for
language A decidable in exponential time, either the class of
languages reducible to A (the lower span) or the class of problems to
which A can be reduced (the upper span) is small in the sense of
resource-bounded measure and, in particular, that the degree of A is
small. Small span theorems have been proven for increasingly stronger
polynomial-time reductions, and a small span theorem for
polynomial-time Turing reductions would imply BPP ≠ EXP. In contrast
to the progress in resource-bounded measure,
Ambos-Spies, Merkle, Reimann, and Stephan (2001)
showed that there is no small span theorem
for the resource-bounded dimension of Lutz (2003), even for
polynomial-time many-one reductions.

Resource-bounded scaled dimension, recently introduced by Hitchcock,
Lutz, and Mayordomo (2004), provides rescalings of
resource-bounded dimension. We use scaled dimension to further
understand the contrast between measure and dimension regarding
polynomial-time spans and degrees. We strengthen prior results by
showing that the small span theorem holds for polynomial-time many-one
reductions in the -3^{rd}-order scaled dimension, but fails to
hold in the -2^{nd}-order scaled dimension. Our results also
hold in exponential space.

As an application, we show that determining the -2^{nd}- or
-1^{st}-order scaled dimension in ESPACE of the many-one
complete languages for E would yield a proof of P = BPP or P ≠
PSPACE. On the other hand, it is shown unconditionally that the
complete languages for E have -3^{rd}-order scaled dimension 0
in ESPACE and -2^{nd}- and -1^{st}-order scaled
dimension 1 in E.

*SIAM Journal on Computing*, 34(1):170-194, 2004.

[PostScript | PDF | DOI link]*Proceedings of the*(Amherst, Massachusetts, June 21-24, 2004), pages 104-112. IEEE Computer Society Press, 2004.*19th IEEE Conference on Computational Complexity*

[DOI link]-
Technical Report cs.CC/0304030,
Computing Research
Repository, 2003.