Weakly hard problems

A weak completeness phenomenon is investigated in the complexity class E=DTIME(2^linear). According to standard terminology, a language H is ⩽_m^P-hard for E if the set P_m(H), consisting of all languages A⩽_m^P H, contains the entire class E. A language C is ⩽_m ^P-complete for E if it is ⩽_m^P-hard for E and is also an element of E. Generalizing this, a language H is weakly ⩽_m^P-hard for E if the set P_m(H) does not have measure 0 in E. A language C is weakly ⩽_m^P-complete for E if it is weakly ⩽_m ^P-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 ⩽_m^P-complete, but not ⩽_m^P -complete, for E. The existence of such languages implies that previously known strong lower bounds on the complexity of weakly ⩽ _m^P-hard problems for E are indeed more general than the corresponding bounds for ⩽_m^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 (i.e. prevent them from winning too much money), while also pursuing another agenda. Martingale diagonalization may be useful for a variety of applications