Separating complexity classes with tally oracles
Authors:
- Lane A. HemachandraLHLane A. Hemachandra
- Roy S. RubinsteinRRRoy S. Rubinstein
Open Access
- 1 January 1992
- journal article
- Published by Elsevier in Theoretical Computer Science
- Vol. 92 (2) , 309-318
Abstract
No abstract availableKeywords
This publication has 26 references indexed in Scilit:
- A uniform approach to define complexity classesTheoretical Computer Science, 1992
- Relativizing relativized computationsTheoretical Computer Science, 1989
- On sparse oracles separating feasible complexity classesInformation Processing Letters, 1988
- Relativizing complexity classes with sparse oraclesJournal of the ACM, 1986
- The polynomial-time hierarchy and sparse oraclesJournal of the ACM, 1986
- Relativized circuit complexityJournal of Computer and System Sciences, 1985
- Strong nondeterministic polynomial-time reducibilitiesTheoretical Computer Science, 1982
- On relativization and the existence of complete sets1982
- Relativized Questions Involving Probabilistic AlgorithmsJournal of the ACM, 1982
- Relative complexity of checking and evaluatingInformation Processing Letters, 1976