Sparse sets in NP-P: EXPTIME versus NEXPTIME
Authors:
- J. HartmanisJHJ. Hartmanis
- N. ImmermanNIN. Immerman
- V. SewelsonVSV. Sewelson
- 1 May 1985
- journal article
- Published by Elsevier in Information and Control
- Vol. 65 (2-3) , 158-181
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