Hard sets are hard to find
type: Item
instance of: scholarly article
title: Hard sets are hard to find
zbMATH Open document ID: 0947.68067
author: Harry Buhrman
author: Dieter Van Melkebeek
published in: Journal of Computer and System Sciences
publication date: 2000-01-17T00:00:00Z
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 1389789
zbMATH Keywords: complete sets
zbMATH Keywords: complexity classes
MaRDI profile type: Publication
cites work: Separating NP-completeness notions under strong hypotheses
cites work: Q4218120
cites work: Genericity and measure for exponential time
cites work: \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
cites work: Q3996675
cites work: Q4321931
cites work: Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
cites work: Compressibility and resource bounded measure
cites work: An excursion to the Kolmogorov random strings
cites work: Q4258582
cites work: On relativized exponential and probabilistic complexity classes
cites work: The Complexity and Distribution of Hard Problems
cites work: Category and Measure in Complexity Classes
cites work: Almost everywhere high nonuniform complexity
cites work: Measure, Stochasticity, and the Density of Hard Languages
cites work: Cook versus Karp-Levin: Separating completeness notions if NP is not small
cites work: Almost every set in exponential time is P-bi-immune
cites work: Hardness vs randomness
cites work: Q4298260
cites work: Q4231907
description: scientific article; zbMATH DE number 1389789