Collapsing oracle-tape hierarchies
Georg Gottlob · 2002
Other authors have shown that equipping a logspace oracle Turing machine with more than one oracle tape may result in an increased computational power. We are interested in the inverse problem: For which oracle classes C does the oracle-tape hierarchy collapse in the sense that logspace machines with a fixed number of oracle tapes cannot compute more than machines with a single oracle tape? Surprisingly, it turns out that for an extremely large number of central complexity classes C, the oracle tape hierarchy for C collapses totally. To show this, we first show that the oracle-tape hierarchy for oracle class C collapses iff C is smooth, i.e., iff it holds that the closure of C under L/sup C/ reductions is equal to L/sup C/ We then derive sufficient conditions for smoothness. In particular, we show that any class C is smooth if it is closed under marked union and positive polynomial-time Turing reductions. We show that our results have applications in finite model theory, and we derive related results on well-known classes of uniform relativized circuits.