Oblivious Symmetric Alternation.

We introduce a new class as a subclass of the symmetric alternation class . An proof system has the flavor of an proof system, but it is more restrictive in nature. In an proof system, we have two competing provers and a verifier such that for any input, the honest prover has an irrefutable certificate. In an proof system, we require that the irrefutable certificates depend only on the length of the input, not on the input itself. In other words, the irrefutable proofs are oblivious of the input. For this reason, we call the new class oblivious symmetric alternation. While this might seem slightly contrived, it turns out that this class helps us improve some existing results. For instance, we show that if then , whereas the best known collapse under the same hypothesis was . We also define classes and , bearing relations to as and are to , and show that these along with form a hierarchy, similar to the polynomial hierarchy. We investigate other inclusions involving these classes and strengthen some known results. For example, we show that which sharpens the known result [16]. Another example is our result that , which is an improved upper bound on . Finally, we also prove better collapses for the 2-queries problem as discussed by [12,1,7]. We prove that . [ABSTRACT FROM AUTHOR]