Collapsing oracle hierarchies, census functions and logarithmically many queries. (English) Zbl 0648.68065

STACS 88, Theoretical aspects of computer science, Proc. 5th Annu. Symp., Bordeaux/France 1988, Lect. Notes Comput. Sci. 294, 91-97 (1988).
[For the entire collection see Zbl 0635.00015.]
It is shown with one common technique that several space-bounded oracle hierarchies and also certain exponential-time oracle hierarchies “collapse” to their respectively level \(\Delta_ 2\), i.e., \(\Delta_ 2=\Sigma_ 2=\Pi_ 2=\Delta_ 3=....\)
The proof uses a technique of counting the census function of the oracle set. The results concerning space-complexity classes are meanwhile superseded by Immerman’s result that NSPACE(s(n)) is closed under complementation, which implies that these hierarchies even collapse to level \(\Sigma_ 1\).
Reviewer: U.Schöning


68Q05 Models of computation (Turing machines, etc.) (MSC2010)


Zbl 0635.00015