Weakly Hard Problems
Jack H. Lutz · SIAM Journal on Computing · 1995
A weak completeness phenomenon is investigated in the complexity class ${\text{E}} = {\text{DTIME}}(2^{{\text{linear}}} )$. According to standard terminology, a language H is $ \leq _m^{\text{P}} $-hard for E if the set ${\text{P}}_m (H)$, consisting of all languages $A \leq _m^{\text{P}} H$, contains the entire class E. A language C is $ \leq _m^{\text{P}} $-complete for E if it is $ \leq _m^{\text{P}} $-hard for E and an element of E. Generalizing this, a language H is weakly$ \leq _m^{\text{P}} $-hard for E if the set ${\text{P}}_m (H)$ does not have measure 0 in E. A language C is weakly$ \leq _m^{\text{P}} $-complete for E if it is weakly $ \leq _m^{\text{P}} $-hard for E and an element of E. The main result of this paper is the construction of a language that is weakly $ \leq _m^{\text{P}} $-complete, but not $ \leq _m^{\text{P}} $-complete, for E. The existence of such languages implies that previously known strong lower bounds on the complexity of weakly $ \leq _m^{\text{P}} $-hard problems for E (given by work of Lutz, Mayordomo, and Juedes) are indeed more general than the corresponding bounds for $ \leq _m^{\text{P}} $-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.