Robust machines accept easy sets
Open Access
- 31 December 1990
- journal article
- research article
- Published by Elsevier in Theoretical Computer Science
- Vol. 74 (2) , 217-225
- https://doi.org/10.1016/0304-3975(90)90138-8
Abstract
No abstract availableKeywords
This publication has 15 references indexed in Scilit:
- On sparse oracles separating feasible complexity classesInformation Processing Letters, 1988
- Complexity classes without machines: On complete languages for UPTheoretical Computer Science, 1988
- Complexity Measures for Public-Key CryptosystemsSIAM Journal on Computing, 1988
- Generic oracles and oracle classesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1987
- Sets with small generalized Kolmogorov complexityActa Informatica, 1986
- Sparse Sets, Lowness and HighnessSIAM Journal on Computing, 1986
- Qualitative relativizations of complexity classesJournal of Computer and System Sciences, 1985
- Quantitative Relativizations of Complexity ClassesSIAM Journal on Computing, 1984
- Strong nondeterministic polynomial-time reducibilitiesTheoretical Computer Science, 1982
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ QuestionSIAM Journal on Computing, 1975