Query Order and Self-Specifying Machines
Lane A. Hemaspaandra, Harald Hempel⋆, Gerd Wechsung · 1995
We study the computational power of machines that specify their own acceptance types, and we show that they accept exactly the languages in R_m^{#P}(NP). We study the effect of query order on computational power, and show that P^{BH_j[1]:BH_k[1]}---the languages computable via a polynomial-time machine given one query to the $j$th level of the boolean hierarchy followed by one query to the $k$th level of the boolean hierarchy---equals R^p_{j+2k--1-tt}(NP) if $j$ is even and $k$ is odd, and equals R^p_{j+2k-tt} otherwise. Thus, unless the polynomial hierarchy collapses, it holds that for each 1 \leq j \leq k: P^{BH_j[1]:BH_k[1]} = P^{BH_k[1]:BH_j[1]} \Longleftrightarrow (j=k) \vee (j is even \wedge k = j+1). We extend our analysis to apply to more general query classes.