The Complexity and Distribution of Hard Problems

DOI10.1137/S0097539792238133zbMath0827.68043OpenAlexW2149767115MaRDI QIDQ4834381

David W. Juedes, Jack H. Lutz

Publication date: 13 December 1995

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539792238133

zbMATH Keywords

complexitydistribution

Mathematics Subject Classification ID

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

Related Items

Equivalence of measures of complexity classes, Genericity and measure for exponential time, An excursion to the Kolmogorov random strings, A note on measuring in P, The size of SPP, Weakly complete problems are not rare, Autoreducibility, mitoticity, and immunity, Resource bounded randomness and weakly complete problems, Hard sets are hard to find, Almost complete sets., Cook versus Karp-Levin: Separating completeness notions if NP is not small, Scaled dimension and the Kolmogorov complexity of Turing-hard sets, On the robustness of ALMOST-$\mathcal {R}$, Genericity and randomness over feasible probability measures, Almost every set in exponential time is P-bi-immune, Genericity and measure for exponential time, Resource bounded randomness and computational complexity