Measure, Stochasticity, and the Density of Hard Languages
From MaRDI portal
Publication:4305356
DOI10.1137/S0097539792237498zbMath0809.68069WikidataQ60578993 ScholiaQ60578993MaRDI QIDQ4305356
Elvira Mayordomo, Jack H. Lutz
Publication date: 20 March 1995
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Related Items (19)
NP-hard sets are superterse unless NP is small ⋮ Equivalence of measures of complexity classes ⋮ Genericity and measure for exponential time ⋮ A note on measuring in P ⋮ The size of SPP ⋮ Weakly complete problems are not rare ⋮ Resource bounded randomness and weakly complete problems ⋮ Dimension, halfspaces, and the density of hard sets ⋮ Hard sets are hard to find ⋮ Cook versus Karp-Levin: Separating completeness notions if NP is not small ⋮ Upward separations and weaker hypotheses in resource-bounded measure ⋮ Comparing nontriviality for E and EXP ⋮ Collapsing and separating completeness notions under average-case and worst-case hypotheses ⋮ Axiomatizing Resource Bounds for Measure ⋮ Genericity and randomness over feasible probability measures ⋮ Weak completeness notions for exponential time ⋮ The zero-one law holds for BPP ⋮ Some structural properties of SAT ⋮ MAX3SAT is exponentially hard to approximate if NP has positive dimension.
This page was built for publication: Measure, Stochasticity, and the Density of Hard Languages