Recommendations
Cites work
- BPP has subexponential time simulations unless EXPTIME has publishable proofs
- Almost every set in exponential time is P-bi-immune
- Almost everywhere high nonuniform complexity
- An excursion to the Kolmogorov random strings
- Category and Measure in Complexity Classes
- Compressibility and resource bounded measure
- Cook versus Karp-Levin: Separating completeness notions if NP is not small
- Genericity and measure for exponential time
- Hardness vs randomness
- scientific article; zbMATH DE number 46423 (Why is no real title available?)
- scientific article; zbMATH DE number 1222581 (Why is no real title available?)
- scientific article; zbMATH DE number 1261804 (Why is no real title available?)
- scientific article; zbMATH DE number 1335891 (Why is no real title available?)
- scientific article; zbMATH DE number 610968 (Why is no real title available?)
- scientific article; zbMATH DE number 719756 (Why is no real title available?)
- Measure, Stochasticity, and the Density of Hard Languages
- On relativized exponential and probabilistic complexity classes
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Separating NP-completeness notions under strong hypotheses
- The Complexity and Distribution of Hard Problems
Cited in
(9)- Scaled dimension and the Kolmogorov complexity of Turing-hard sets
- Almost complete sets.
- Randomness and completeness in computational complexity
- Nonuniform reductions and NP-completeness
- Generic density and small span theorem
- Nonuniform reductions and NP-completeness
- scientific article; zbMATH DE number 1335891 (Why is no real title available?)
- scientific article; zbMATH DE number 1500533 (Why is no real title available?)
- Genericity and measure for exponential time (extended abstract)
This page was built for publication: Hard sets are hard to find
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1961379)
