Measure, Stochasticity, and the Density of Hard Languages

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)

zbMATH Keywords

computational complexitybounded measuredense languagessparse languagesweak stochasticity

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

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