Weakly complete problems are not rare

Certain natural decision problems are known to be intractable because they are complete for E, the class of all problems decidable in exponential time. Lutz recently conjectured that many other seemingly intractable problems are not complete for E, but are intractable nonetheless because they areweakly complete for E (i.e., they are in E and hard for more than a measure 0 subset of E). The main result of this paper shows that Lutz's intuition is at least partially correct: many more problems are weakly complete for E than are complete for E.The main result of this paper states that weakly complete problems arenot rare in the sense that they form a non-measure 0 subset of E. This extends a recent result of Lutz that establishes the existence of problems that are weakly complete, but not complete, for E. The proof of Lutz's original result employs a sophisticatedmartingale diagonalization argument. Here, we simplify and extend Lutz's argument to prove the main result. This simplified martingale diagonalization argument may be applicable to other questions involving individual weakly complete problems.