Query Order
| dc.creator | Hemaspaandra, Lane A. | |
| dc.creator | Hempel, Harald | |
| dc.creator | Wechsung, Gerd | |
| dc.date | 1999-09-30 | |
| dc.date.accessioned | 2026-07-07T03:24:22Z | |
| dc.date.available | 2026-07-07T03:24:22Z | |
| dc.description | 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. | |
| dc.description | 18 pages, 1 figure (earlier version appears as UR-CS-TR-95-596) | |
| dc.identifier | https://arxiv.org/abs/cs/9909020 | |
| dc.identifier | http://arxiv.org/abs/cs/9909020 | |
| dc.identifier | SIAM Journal on Computing, 28, 637-651, 1999 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/33299 | |
| dc.subject | Computational Complexity | |
| dc.subject | F.1.3 | |
| dc.title | Query Order | |
| dc.type | text |