Measure, Stochasticity, and the Density of Hard Languages

Abstract

The main theorem of this paper is that, for every real number $\alpha < 1$ (e.g., $\alpha = 0.99$), only a measure 0 subset of the languages decidable in exponential time are $ \leqslant _{n^\alpha - tt}^{\text{p}} $-reducible to languages that are not exponentially dense. Thus every$ \leqslant _{n^\alpha - tt}^{\text{p}} $hard language for E is exponentially dense. This strengthens Watanabe’s 1987 result, that every $ \leqslant _{(\log n) - tt}^{\text{p}} $-hard language for E is exponentially dense. The combinatorial technique used here, the sequentially most frequent query selection, also gives a new, simpler proof of Watanabe’s result. The main theorem also has implications for the structure of NP under strong hypotheses. Ogiwara and Watanabe (1991) have shown that the hypothesis ${\text{P}} \ne {\text{NP}}$ implies that every $ \leqslant _{btt}^{\text{p}} $ -hard language for NP is nonsparse (i.e., not polynomially sparse). Their technique does not appear to allow significant relaxation of either the query bound or the sparseness criterion. It is shown here that a stronger hypothesis—namely, that NP does not have measure 0 in exponential time—implies the stronger conclusion that, for every real $\alpha < 1$, every $ \leqslant _{n^\alpha - tt}^{\text{p}} $-hard language for NP is exponentially dense. Evidence is presented that this stronger hypothesis is reasonable. The proof of the main theorem uses a new, very general weak stochasticity theorem, ensuring that almost every language in E is statistically unpredictable by feasible deterministic algorithms, even with linear nonuniform advice.