1999/09/30 by Lane A. Hemaspaandra, Harald Hempel, Gerd Wechsung
Computer Science · #cs.CC
published as SIAM Journal on Computing, 28, 637-651, 1999 · 18 pages, 1 figure (earlier version appears as UR-CS-TR-95-596)
arxiv created 1999/09/30 · arxiv updated 2009/11/30
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 \redttnpj+2k-1 if j is even and k is odd, and equals \redttnpj+2k otherwise. Thus, unless the polynomial hierarchy collapses, it holds that for each 1≤ j ≤ k: \pjk = \pkj \iff (j=k) ∨ (jis even ∧ k=j+1). We extend our analysis to apply to more general query classes.