Abstract of Paper

Measure Theoretic Completeness Notions for the Exponential Time Classes
by Klaus Ambos-Spies

Abstract:

The resource­bounded measure theory of Lutz leads to weakenings of the
classical hardness and completeness notions. While a set $A$ is hard (under
polynomial­time many­one reducibility) for a complexity class $C$ if every
set in $C$ can be reduced to $A$, a set $A$ is almost hard if the class of
reducible sets has measure 1 in $C$, and a set $A$ is weakly hard if the
class of reducible sets does not have measure 0 in $C$. If, in addition, $A$
is a member of $C$ then $A$ is almost complete and weakly complete for $C$,
respectively. Weak hardness for the exponential time classes
E${}={}$DTIME$(2^{\mbox{lin}(n)})$ and
EXP${}={}$DTIME$(2^{\mbox{poly}(n)})$ has been extensively studied in the
literature, whereas the nontriviality of the concept of almost completeness
has been established only recently.

Here we continue the investigation of these measure theoretic hardness
notions.

In the first part of this paper we establish the relations among these
notions which had been left open. In particular, we show that almost
hardness for $E$ and EXP are independent. Moreover, there is a set in $E$
which is almost complete for EXP but not weakly complete for $E$. These
results exhibit a surprising degree of independence of the measure concepts
for $E$ and EXP.

In the second part of the paper we give structural separations of
completeness and almost completeness in terms of immunity, and of almost
completeness and weak completeness in terms of incompressibility. Moreover,
we look at almost completeness for the exponential­time classes under
bounded­truth­table and Turing reductions of fixed norm: We establish the
nontriviality of these concepts and prove some hierachy theorems.