Weakly Complete Problems are Not Rare

Juedes, David (1994) Weakly Complete Problems are Not Rare. Technical Report TR94-10, Department of Computer Science, Iowa State University.

Abstract

Weakly Complete Problems are Not Rare
David W. Juedes
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 are weakly complete for 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 are
not 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 sophisticated martingale
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.


Subjects:
All uncategorized technical reports


ID code:
00000076
Deposited by:
Staff Account on 06 September 1994





Contact site administrator at: ssg@cs.iastate.edu