Measure, Stochasticity, and the Density of Hard Languages

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.

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


Subjects:
All uncategorized technical reports


ID code:
00000019
Deposited by:
Staff Account on 01 May 1992





Contact site administrator at: ssg@cs.iastate.edu