Symmetric Alternation Captures BPP
Author(s)
Russell, Alexander; Sundaram, Ravi![Thumbnail](/bitstream/handle/1721.1/149253/MIT-LCS-TM-541.pdf.jpg?sequence=3&isAllowed=y)
DownloadMIT-LCS-TM-541.pdf (769.0Kb)
Metadata
Show full item recordAbstract
We introduce the natural class Sp2 containing those languages which may be expressed in terms of two symmetric quantifiers. This class lies between ? and ? and naturally generates a "symmetric" hierarchy corresponding to the polynomial-time hierarchy. We demonstrate, using the probabilistic method, new containment theorems for BPP.
Date issued
1995-11Series/Report no.
MIT-LCS-TM-541