Abstract
The main theorem of this paper is that, for every real number α<1 (e.g., α=0.99), only a measure 0 subset of the languages decidable in exponential time are \(\leqslant _{n^\alpha - tt}^P\)-reducible to languages that are not exponentially dense. Thus every \(\leqslant _{n^\alpha - tt}^P\)-hard language for E is exponentially dense. This strengthens Watanabe's 1987 result, that every ≤ PO(log n)-tt -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 P ≠ NP implies that every ≤ Pbtt -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 α<1, every \(\leqslant _{n^\alpha - tt}^P\)-hard language for NP is exponentially dense. Evidence is presented that this stronger hypothesis is reasonable.
Also presented here (and used in proving the main theorem) is a weak stochasticity theorem, ensuring that almost every language in E is statistically unpredictable by feasible deterministic algorithms, even with linear nonuniform advice.
This author's research was supported in part by National Science Foundation Grant CCR-9157382, with matching funds from Rockwell International, and in part by DIMACS, where he was a visitor during the first phase of this work.
This author's research, performed while visiting Iowa State University, was supported in part by the ESPRIT EC project 3075 (ALCOM), in part by National Science Foundation Grant CCR-9157382, and in part by Spanish Government grant FPI PN90.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
N. Alon and J. H. Spencer, The Probabilistic Method, Wiley, 1992.
V. Arvind, J. Köbler, and M. Mundhenk, Bounded truth-table and conjunctive reductions to sparse and tally sets, Technical report. University of Ulm, 1992. Technical Report Ulmer Informatik-Berichte 92-01.
L. Berman and J. Hartmanis, On isomorphism and density of NP and other complete sets, SIAM Journal on Computing 6 (1977), pp. 305–322.
P. Erdös, Some remarks on the theory of graphs, Bulletin of the American Mathematical Society 53 (1947), pp. 292–294.
P. Erdös and J. Spencer, Probabilistic Methods in Combinatorics, Academic Press, New York, 1974.
B. Fu, With quasi-linear queries EXP is not polynomial time Turing reducible to sparse sets, manuscript, August 1992.
L. A. Hemachandra, M. Ogiwara, and O. Watanabe, How hard are sparse sets?, Proceedings of the Seventh Annual Structure in Complexity Theory Conference, 1992, pp. 222–238. IEEE Press.
D. W. Juedes and J. H. Lutz, The complexity and distribution of hard problems, Technical Report 92-23, Department of Computer Science, Iowa State University, 1992. Submitted.
D. W. Juedes and J. H. Lutz, Kolmogorov complexity, complexity cores, and the distribution of hardness, In O. Watanabe, editor, Kolmogorov Complexity and Computational Complexity. Springer-Verlag, 1992, pp. 43–65.
R. M. Karp and R. J. Lipton, Some connections between nonuniform and uniform complexity classes, Proceedings of the 12th ACM Symposium on Theory of Computing, 1980, pp. 302–309, also published as Turing machines that take advice, L'Enseignement Mathematique 28 (1982), pp. 191–209.
A. N. Kolmogorov and V. A. Uspenskii, Algorithms and randomness, translated in Theory of Probability and its Applications 32 (1987), pp. 389–412.
J. H. Lutz, Intrinsically pseudorandom sequences, in preparation.
J. H. Lutz, Resource-bounded measure, in preparation.
J. H. Lutz, An upward measure separation theorem, Theoretical Computer Science 81 (1991), pp. 127–135.
J. H. Lutz, Almost everywhere high nonuniform complexity, Journal of Computer and System Sciences 44 (1992), pp. 220–258.
J. H. Lutz and E. Mayordomo. Measure, stochasticity, and the density of hard languages. Technical Report 92-11, Department of Computer Science, Iowa State University, 1992. Submitted.
J. H. Lutz and W. J. Schmidt, Circuit size relative to pseudorandom oracles, Theoretical Computer Science A 107 (1993), to appear.
S. R. Mahaney, Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis, Journal of Computer and System Sciences 25 (1982), pp. 130–143.
E. Mayordomo, Almost every set in exponential time is P-bi-immune, Seventeenth International Symposium on Mathematical Foundations of Computer Science, 1992. Springer-Verlag, to appear.
A. R. Meyer, 1977, reported in [3].
M. Ogiwara and O. Watanabe, On polynomial bounded truth-table reducibility of NP sets to sparse sets, SIAM Journal on Computing 20 (1991), pp. 471–483.
A. L. Selman, 1992, personal communication.
C. E. Shannon, A mathematical theory of communication, Bell System Technical Journal 27 (1948), pp. 379–423, 623–656.
C. E. Shannon, The synthesis of two-terminal switching circuits, Bell System Technical Journal 28 (1949), pp. 59–98.
J. H. Spencer, Ten Lectures on the Probabilistic Method, SIAM, 1987.
L. J. Stockmeyer, The polynomial-time hierarchy, Theoretical Computer Science 3 (1977), pp. 1–22.
V. A. Uspenskii, A. L. Semenov, and A. Kh. Shen', Can an individual sequence of zeros and ones be random?, Russian Mathematical Surveys 45 (1990), pp. 121–189.
O. Watanabe, On the Structure of Intractable Complexity Classes, PhD thesis, Tokyo Institute of Technology, 1987.
O. Watanabe, Polynomial time reducibility to a set of small density, Proceedings of the Second Structure in Complexity Theory Conference, 1987, pp. 138–146.
C. B. Wilson, Relativized circuit complexity, Journal of Computer and System Sciences 31 (1985), pp. 169–181.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lutz, J.H., Mayordomo, E. (1993). Measure, stochasticity, and the density of hard languages. In: Enjalbert, P., Finkel, A., Wagner, K.W. (eds) STACS 93. STACS 1993. Lecture Notes in Computer Science, vol 665. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-56503-5_6
Download citation
DOI: https://doi.org/10.1007/3-540-56503-5_6
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-56503-1
Online ISBN: 978-3-540-47574-3
eBook Packages: Springer Book Archive