On sparse oracles separating feasible complexity classes
- 1 January 1986
- book chapter
- Published by Springer Nature
- p. 321-333
- https://doi.org/10.1007/3-540-16078-7_86
Abstract
No abstract availableKeywords
This publication has 11 references indexed in Scilit:
- Computation times of NP sets of different densitiesTheoretical Computer Science, 1984
- Generalized Kolmogorov complexity and the structure of feasible computationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1983
- Some consequences of non-uniform conditions on uniform classesTheoretical Computer Science, 1983
- On self-reducibility and weak P-selectivityJournal of Computer and System Sciences, 1983
- Parity, circuits, and the polynomial-time hierarchyPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1981
- AlternationJournal of the ACM, 1981
- Sparse complete sets for NP: Solution of a conjecture of Berman and HartmanisPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1980
- Some connections between nonuniform and uniform complexity classesPublished by Association for Computing Machinery (ACM) ,1980
- Complete sets and the polynomial-time hierarchyTheoretical Computer Science, 1976
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ QuestionSIAM Journal on Computing, 1975