Measure, Stochasticity, and the Density of Hard Languages







Deposit Papers 


Lutz, Jack H. and Mayordomo, Elvira (1992) Measure, Stochasticity, and the Density of Hard Languages. Technical Report TR92-13, Department of Computer Science, Iowa State University.

Full text available as:Postscript
Adobe PDF


Measure, Stochasticity, and the Density of Hard Languages
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
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

Subjects:All uncategorized technical reports
ID code:00000019
Deposited by:Staff Account on 01 May 1992

Contact site administrator at: