Details

Autor(en) / Beteiligte

• LUTZ, J. H

Titel

Weakly hard problems

Ist Teil von

• SIAM journal on computing, 1995-12, Vol.24 (6), p.1170-1189

Ort / Verlag

Philadelphia, PA: Society for Industrial and Applied Mathematics

Erscheinungsjahr

1995

Link zum Volltext

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• 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.