Nonlevelable sets and immune sets in the accepting density hierarchy inNP
Author:
- 1 December 1985
- journal article
- research article
- Published by Springer Nature in Theory of Computing Systems
- Vol. 18 (1) , 189-205
Abstract
No abstract availableKeywords
This publication has 32 references indexed in Scilit:
- Bi-immune sets for complexity classesTheory of Computing Systems, 1985
- The structure of polynomial complexity cores1984
- Relativized Questions Involving Probabilistic AlgorithmsJournal of the ACM, 1982
- 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 counting problems and the polynomial-time hierarchyTheoretical Computer Science, 1980
- Two theorems on random polynomial time1978
- Separating Nondeterministic Time Complexity ClassesJournal of the ACM, 1978
- On Isomorphisms and Density of $NP$ and Other Complete SetsSIAM Journal on Computing, 1977
- On the structure of complete sets: Almost everywhere complexity and infinitely often speedup1976
- On Reducibility to Complex or Sparse SetsJournal of the ACM, 1975