

Lutz, Jack H. and Mayordomo, Elvira (1992) Measure, Stochasticity, and the Density of Hard Languages. Technical Report TR9213, Department of Computer Science, Iowa State University.
Abstract
Measure, Stochasticity, and the Density of Hard Languages
by
Jack H. Lutz and Elvira Mayordomo
Ogiwara and Watanabe have recently shown that the hypothesis P not
equal NP implies that no (polynomially) sparse language is
polynomialtime btthard 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 tablereducible to languages that are not exponentially
dense.
Contact site administrator at: ssg@cs.iastate.edu
