Hard sets are hard to find
From MaRDI portal
Publication:1961379
zbMath0947.68067MaRDI QIDQ1961379
Dieter van Melkebeek, Harry Buhrman
Publication date: 17 January 2000
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Related Items (4)
Unnamed Item ⋮ Nonuniform reductions and NP-completeness ⋮ Generic density and small span theorem ⋮ Scaled dimension and the Kolmogorov complexity of Turing-hard sets
Cites Work
- Cook versus Karp-Levin: Separating completeness notions if NP is not small
- Almost everywhere high nonuniform complexity
- \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
- Hardness vs randomness
- Almost every set in exponential time is P-bi-immune
- Genericity and measure for exponential time
- An excursion to the Kolmogorov random strings
- Category and Measure in Complexity Classes
- 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
- Measure, Stochasticity, and the Density of Hard Languages
- Compressibility and resource bounded measure
- The Complexity and Distribution of Hard Problems
- Separating NP-completeness notions under strong hypotheses
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Hard sets are hard to find
