On the relative complexity of hard problems for complexity classes without complete problems
- 31 January 1989
- journal article
- Published by Elsevier in Theoretical Computer Science
- Vol. 63 (1) , 43-61
- https://doi.org/10.1016/0304-3975(89)90066-2
Abstract
No abstract availableKeywords
This publication has 13 references indexed in Scilit:
- A note on complete problems for complexity classesInformation Processing Letters, 1986
- Sublattices of the polynomial time degreesInformation and Control, 1985
- Computation times of NP sets of different densitiesTheoretical Computer Science, 1984
- Sparse complete sets for NP: Solution of a conjecture of Berman and HartmanisJournal of Computer and System Sciences, 1982
- A uniform approach to obtain diagonal sets in complexity classesTheoretical Computer Science, 1982
- On the structure of sets in NP and other complexity classesTheoretical Computer Science, 1981
- A note on structure and looking back applied to the relative complexity of computable functionsJournal of Computer and System Sciences, 1981
- P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNPTheory of Computing Systems, 1979
- Computational Complexity of Probabilistic Turing MachinesSIAM Journal on Computing, 1977
- On the Structure of Polynomial Time ReducibilityJournal of the ACM, 1975