Symmetric Alteration Captures BPP
| dc.contributor.author | Russell, Alexander | en_US |
| dc.contributor.author | Sundaram, Ravi | en_US |
| dc.date.accessioned | 2023-03-29T14:38:43Z | |
| dc.date.available | 2023-03-29T14:38:43Z | |
| dc.date.issued | 1995-11 | |
| dc.identifier.uri | https://hdl.handle.net/1721.1/149237 | |
| dc.description.abstract | We introduce the natural class Sp2 containing those languages which may be expressed terms of two symmetric quantifiers. This class lies between ?p2 and ? and naturally generates a "symmetric" hierarchy corresponding to the polynomial-time hierarchy. We demonstrate, using the probabilistic method, new containment theorems for BPP. | en_US |
| dc.relation.ispartofseries | MIT-LCS-TM-520 | |
| dc.title | Symmetric Alteration Captures BPP | en_US |
