Query Order
<|reference_start|>Query Order: We study the effect of query order on computational power, and show that $\pjk$-the languages computable via a polynomial-time machine given one query to the jth level of the boolean hierarchy followed by one query to the kth level of the boolean hierarchy-equals $\redttnp{j+2k-1}$ if j is even and k is odd, and equals $\redttnp{j+2k}$ otherwise. Thus, unless the polynomial hierarchy collapses, it holds that for each $1\leq j \leq k$: $\pjk = \pkj \iff (j=k) \lor (j{is even} \land k=j+1)$. We extend our analysis to apply to more general query classes.<|reference_end|>
@article{hemaspaandra1999query,
    title={Query Order},
    author={Lane A. Hemaspaandra, Harald Hempel, and Gerd Wechsung},
    journal={SIAM Journal on Computing, 28, 637-651, 1999},
    year={1999},
    archivePrefix={arXiv},
    eprint={cs/9909020},
    primaryClass={cs.CC}
}