QUERY ORDER

We study the effect of query order on computational power and show tha t P-BH j[1]:BHk[1] -the languages computable via a polynomial-time mac hine given one query to the jth level of the boolean hierarchy followe d by one query to the kth level of the boolean hierarchy-equals R-j+2k -1-tt(p) (NP) if j is even and k is odd and equals R-j+2k-tt(p) (NP) o therwise. Thus unless the polynomial hierarchy collapses it holds that , for each 1 less than or equal to j less than or equal to k, P-BH j[1 ]:BHk[1] = P-BH k[1]:BH j[1] double left right arrow (j = k) boolean O R (j is even boolean AND k = j + 1). We extend our analysis to apply t o more general query classes.