The Complexity and Distribution of Hard Problems

DOI10.1137/S0097539792238133MaRDI QIDQ4834381zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• On the complexity of computational problems regarding distributions
• The complexity of distributions
• scientific article; zbMATH DE number 403953
• Complexity of distributions and average-case hardness
• scientific article; zbMATH DE number 1306886
• scientific article; zbMATH DE number 1775419
• Some Observations about the Randomness of Hard Problems
• Hardness of fully dense problems

Cited in

(25)

• Scaled dimension and the Kolmogorov complexity of Turing-hard sets
• Genericity and randomness over feasible probability measures
• Genericity and measure for exponential time
• An excursion to the Kolmogorov random strings
• Resource bounded randomness and weakly complete problems
• Almost complete sets.
• Resource bounded randomness and computational complexity
• Weakly complete problems are not rare
• Hard sets are hard to find
• Hardness of fully dense problems
• The coincidence of the classes of problems solvable by deterministic algorithms bounded by exponential time and polynomial space
• scientific article; zbMATH DE number 512813 (Why is no real title available?)
• Measure, Stochasticity, and the Density of Hard Languages
• scientific article; zbMATH DE number 1072536 (Why is no real title available?)
• On the robustness of ALMOST-$\mathcal {R}$
• scientific article; zbMATH DE number 841094 (Why is no real title available?)
• Equivalence of measures of complexity classes
• Almost every set in exponential time is P-bi-immune
• Genericity and measure for exponential time (extended abstract)
• Relation between the hardness of a problem and the number of its solutions
• scientific article; zbMATH DE number 5234254 (Why is no real title available?)
• A note on measuring in P
• The size of SPP
• Cook versus Karp-Levin: Separating completeness notions if NP is not small
• Autoreducibility, mitoticity, and immunity

This page was built for publication: The Complexity and Distribution of Hard Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4834381)