Hard sets are hard to find (Q1961379)

From MaRDI portal

Jump to:navigation, search

scientific article

Language	Label	Description	Also known as
English	Hard sets are hard to find	scientific article

Statements

scholarly article

0 references

Hard sets are hard to find (English)

0 references

0 references

Dieter van Melkebeek

0 references

Journal of Computer and System Sciences

0 references

publication date

17 January 2000

0 references

zbMATH Keywords

complete sets

0 references

complexity classes

0 references

MaRDI profile type

MaRDI publication profile

0 references

Separating NP-completeness notions under strong hypotheses

0 references

0 references

Genericity and measure for exponential time

0 references

\(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs

0 references

0 references

0 references

Relative to a Random Oracle<i>A</i>, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1

0 references

Compressibility and resource bounded measure

0 references

An excursion to the Kolmogorov random strings

0 references

0 references

On relativized exponential and probabilistic complexity classes

0 references

The Complexity and Distribution of Hard Problems

0 references

Category and Measure in Complexity Classes

0 references

Almost everywhere high nonuniform complexity

0 references

Measure, Stochasticity, and the Density of Hard Languages

0 references

Cook versus Karp-Levin: Separating completeness notions if NP is not small

0 references

Almost every set in exponential time is P-bi-immune

0 references

Hardness vs randomness

0 references

0 references

0 references

Identifiers

zbMATH Open document ID

0 references

Mathematics Subject Classification ID

0 references

zbMATH DE Number

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1961379

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Item:Q1961379&oldid=34233470"