Sparse sets in NP-P: EXPTIME versus NEXPTIME
- 30 June 1985
- journal article
- Published by Elsevier in Information and Control
- Vol. 65 (2-3), 158-181
- https://doi.org/10.1016/s0019-9958(85)80004-8
Abstract
No abstract availableKeywords
This publication has 13 references indexed in Scilit:
- On relativized exponential and probabilistic complexity classesInformation and Control, 1986
- Sparse complete sets for NP: Solution of a conjecture of Berman and HartmanisJournal of Computer and System Sciences, 1982
- A second step toward the polynomial hierarchyTheoretical Computer Science, 1979
- Inclusion complete tally languages and the Hartmanis-Berman conjectureTheory of Computing Systems, 1977
- Techniques for separating space complexity classesJournal of Computer and System Sciences, 1977
- The polynomial-time hierarchyTheoretical Computer Science, 1976
- On the Structure of Polynomial Time ReducibilityJournal of the ACM, 1975
- Tally languages and complexity classesInformation and Control, 1974
- A hierarchy for nondeterministic time complexityJournal of Computer and System Sciences, 1973
- A Note Concerning Nondeterministic Tape ComplexitiesJournal of the ACM, 1972