Query order in the polynomial hierarchy
| Author(s) : | Harald Hempel Lane A. Hemaspaandra Edith Hemaspaandra, |
| Publisher : | N/A |
| Publication Date : | 1998 |
| ISSN : | N/A |
| Abstract : | We study query order within the polynomial hierarchy. P C:D denotes the class of languages computable by a polynomial-time machine that is allowed one query to C followed by one query to D [HHW]. We prove that the levels of the polynomial hierarchy are order-oblivious: P \Sigma, |