Lutz, Jack H. (1993) Weakly Hard Problems. Technical Report TR93-13, Department of Computer Science, Iowa State University.
Weakly Hard Problems
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 polynomial-time many-one hard for E if the set Pm(H), consisting of
all languages A that are polynomial-time many-one reducible to H,
contains the entire class E. A language C is polynomial-time many-one
complete for E if it is polynomial-time many-one hard for E and is
also an element of E. Generalizing this, a language H is weakly
polynomial-time many-one hard for E if the set Pm(H) does not have
measure 0 in E. A language C is weakly polynomial-time many-one
complete for E if it is weakly polynomial-time many-one 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 polynomial-time many-one complete, but not polynomial-time
many-one complete, for E. The existence of such languages implies that
previously known strong lower bounds on the complexity of weakly
polynomial-time many-one hard problems for E (given by work of Lutz,
Mayordomo, and Juedes) are indeed more general than the corresponding
bounds for polynomial-time many-one 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: email@example.com