Symmetric alternation captures BPP

We introduce the natural class S-2(P) containing those languages that may b e expressed in terms of two symmetric quantifiers. This class lies between Delta(2)(P) and Sigma(2)(P) boolean AND Pi(2)(P) and naturally generates a "symmetric" hierarchy corresponding to the polynomial-time hierarchy. We de monstrate, using the probabilistic method, new containment theorems for BPP . We show that MA land hence BPP) lies within S2P, improving the constructi ons of Sipser and Lautemann which show that BPP subset of or equal to Sigma (2)(P) boolean AND Pi(2)(P). Symmetric alternation is shown to enjoy two st rong structural properties which are used to prove the desired containment results. We offer some evidence that S-2(P) not equal Sigma(2)(P) boolean A ND Pi(2)(P) by constructing an oracle O such that S-2(P,O) not equal Sigma( 2)(P,O) boolean AND Pi(2)(P,O), assuming that the machines make only "posit ive" oracle queries.