

Lutz, Jack H. (1993) Weakly Hard Problems. Technical Report TR9313, Department of Computer Science, Iowa State University.
Abstract
Weakly Hard Problems
by
Jack H. Lutz
A weak completeness phenomenon is investigated in the complexity class
E= DTIME(2^linear). According to standard terminology, a language H
is polynomialtime manyone hard for E if the set Pm(H), consisting of
all languages A that are polynomialtime manyone reducible to H,
contains the entire class E. A language C is polynomialtime manyone
complete for E if it is polynomialtime manyone hard for E and is
also an element of E. Generalizing this, a language H is weakly
polynomialtime manyone hard for E if the set Pm(H) does not have
measure 0 in E. A language C is weakly polynomialtime manyone
complete for E if it is weakly polynomialtime manyone hard for E and
is also an element of E.
The main result of this paper is the construction of a language that
is weakly polynomialtime manyone complete, but not polynomialtime
manyone complete, for E. The existence of such languages implies that
previously known strong lower bounds on the complexity of weakly
polynomialtime manyone hard problems for E (given by work of Lutz,
Mayordomo, and Juedes) are indeed more general than the corresponding
bounds for polynomialtime manyone hard problems for E.
The proof of this result introduces a new diagonalization method,
called martingale diagonalization. Using this method, one
simultaneously develops an infinite family of polynomial time
computable martingales (betting strategies) and a corresponding family
of languages that defeat these martingales (prevent them from winning
too much money) while also pursuing another agenda. Martingale
diagonalization may be useful for a variety of applications.
Contact site administrator at: ssg@cs.iastate.edu
