Measure, Stochasticity, and the Density of Hard Languages

Abstract

<p>Ogiwara and Watanabe have recently shown that the hypothesis P not equal NP implies that no (polynomially) sparse language is polynomial-time btt-hard for NP. 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 polynomial time n^alpha truth table -hard language for NP is (exponentially) dense. The proof of this fact also yields two absolute results (not involving unproven hypotheses) concerning the structure of exponential time: First, almost every language decidable in exponential time has a stochasticity property, ensuring that it is statistically unpredictable by feasible deterministic algorithms, even with linear nonuniform advice. Second, for alpha < 1, only a measure 0 subset of the languages decidable in exponential time are polynomial time n^alpha truth table-reducible to languages that are not exponentially dense.</p>