Collapsing oracle hierarchies, census functions and logarithmically many queries
- 25 January 2006
- book chapter
- Published by Springer Nature
Abstract
No abstract availableKeywords
This publication has 9 references indexed in Scilit:
- Two remarks on the power of countingPublished by Springer Nature ,2005
- Nondeterministic space is closed under complementationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- PNP [log n] and Sparse Turing-Complete Sets for NPPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1987
- A Structural Theorem that Depends Quantitatively on the Complexity of SATPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1987
- The strong exponential hierarchy collapsesPublished by Association for Computing Machinery (ACM) ,1987
- The complexity of optimization problemsPublished by Association for Computing Machinery (ACM) ,1986
- Space-bounded hierarchies and probabilistic computationsJournal of Computer and System Sciences, 1984
- Sparse complete sets for NP: Solution of a conjecture of Berman and HartmanisJournal of Computer and System Sciences, 1982
- Relativization of questions about log space computabilityTheory of Computing Systems, 1976