Query Order

Details Query Order Query Order

1999-09-30

arxiv.org/abs/cs/9909020v1

SIAM Journal on Computing, 28, 637-651, 1999

Computer Science

Computational Complexity

18 pages, 1 figure (earlier version appears as UR-CS-TR-95-596)

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Query Order does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Query Order, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Query Order will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-570553