Bi-immune sets for complexity classes
- 1 December 1985
- journal article
- research article
- Published by Springer Nature in Theory of Computing Systems
- Vol. 18 (1) , 1-10
- https://doi.org/10.1007/bf01699457
Abstract
No abstract availableKeywords
This publication has 16 references indexed in Scilit:
- Generalized Kolmogorov complexity and the structure of feasible computationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1983
- Oracle-dependent properties of the lattice of NP setsTheoretical Computer Science, 1983
- Completeness, Approximation and DensitySIAM Journal on Computing, 1981
- 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 splitting recursive setsJournal of Computer and System Sciences, 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 speedupPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1976
- A comparison of polynomial time reducibilitiesTheoretical Computer Science, 1975
- On Reducibility to Complex or Sparse SetsJournal of the ACM, 1975
- Une généralisation de la notion d'ensemble immuneRevue française d'automatique informatique recherche opérationnelle. Informatique théorique, 1974