Measure, Stochasticity, and the Density of Hard Languages
- 1 August 1994
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 23 (4) , 762-779
- https://doi.org/10.1137/s0097539792237498
Abstract
No abstract availableKeywords
This publication has 20 references indexed in Scilit:
- The Complexity and Distribution of Hard ProblemsSIAM Journal on Computing, 1995
- On bounded truth-table, conjunctive, and randomized reductions to sparse setsPublished by Springer Nature ,1992
- Kolmogorov Complexity, Complexity Cores, and the Distribution of HardnessPublished by Springer Nature ,1992
- An upward measure separation theoremTheoretical Computer Science, 1991
- Category and Measure in Complexity ClassesSIAM Journal on Computing, 1990
- A guided tour of chernoff boundsInformation Processing Letters, 1990
- Algorithms and RandomnessTheory of Probability and Its Applications, 1988
- On Isomorphisms and Density of $NP$ and Other Complete SetsSIAM Journal on Computing, 1977
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of ObservationsThe Annals of Mathematical Statistics, 1952
- Some remarks on the theory of graphsBulletin of the American Mathematical Society, 1947