The Complexity and Distribution of Hard Problems
- 1 April 1995
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 24 (2) , 279-295
- https://doi.org/10.1137/s0097539792238133
Abstract
No abstract availableThis publication has 20 references indexed in Scilit:
- Structural Complexity IIPublished by Springer Nature ,1990
- On inefficient special cases of NP-complete problemsTheoretical Computer Science, 1989
- Structural Complexity IPublished by Springer Nature ,1988
- The existence and density of generalized complexity coresJournal of the ACM, 1987
- On solving hard problems by polynomial-size circuitsInformation Processing Letters, 1987
- Randomness, relativizations, and polynomial reducibilitiesPublished by Springer Nature ,1986
- Bi-immune sets for complexity classesTheory of Computing Systems, 1985
- Hard-core theorems for complexity classesJournal of the ACM, 1985
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1SIAM Journal on Computing, 1981
- On Isomorphisms and Density of $NP$ and Other Complete SetsSIAM Journal on Computing, 1977