Polynomial-time 1-Turing reductions from #PH to #P
- 22 June 1992
- journal article
- Published by Elsevier in Theoretical Computer Science
- Vol. 100 (1) , 205-221
- https://doi.org/10.1016/0304-3975(92)90369-q
Abstract
No abstract availableKeywords
This publication has 26 references indexed in Scilit:
- Relativizing complexity classes with sparse oraclesJournal of the ACM, 1986
- The polynomial-time hierarchy and sparse oraclesJournal of the ACM, 1986
- NP is as easy as detecting unique solutionsTheoretical Computer Science, 1986
- BPP and the polynomial hierarchyInformation Processing Letters, 1983
- AlternationJournal of the ACM, 1981
- The complexity of computing the permanentTheoretical Computer Science, 1979
- Complete sets and the polynomial-time hierarchyTheoretical Computer Science, 1976
- The polynomial-time hierarchyTheoretical Computer Science, 1976
- Relative complexity of checking and evaluatingInformation Processing Letters, 1976
- Characterizations of Pushdown Machines in Terms of Time-Bounded ComputersJournal of the ACM, 1971