Relative to a random oracle, NP is not small
- 17 December 2002
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 162-174
- https://doi.org/10.1109/sct.1994.315807
Abstract
No abstract availableKeywords
This publication has 17 references indexed in Scilit:
- The complexity and distribution of hard problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- The Complexity of Decision Versus SearchSIAM Journal on Computing, 1994
- Cook versus Karp-Levin: Separating completeness notions if NP is not smallPublished by Springer Nature ,1994
- IP = PSPACEJournal of the ACM, 1992
- Completeness for nondeterministic complexity classesTheory of Computing Systems, 1991
- Can an individual sequence of zeros and ones be random?Russian Mathematical Surveys, 1990
- Structural complexity theory: Recent surprisesPublished by Springer Nature ,1990
- A comparison of polynomial time completeness notionsTheoretical Computer Science, 1987
- On the random oracle hypothesisInformation and Control, 1983
- Completeness, Approximation and DensitySIAM Journal on Computing, 1981