Symmetric Alternation Captures BPP
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 probabilist...
| Main Authors: | , |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149253 |
| _version_ | 1826190970219134976 |
|---|---|
| author | Russell, Alexander Sundaram, Ravi |
| author_facet | Russell, Alexander Sundaram, Ravi |
| author_sort | Russell, Alexander |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T08:48:05Z |
| id | mit-1721.1/149253 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T08:48:05Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1492532023-03-30T04:17:45Z Symmetric Alternation Captures BPP Russell, Alexander Sundaram, Ravi 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. 2023-03-29T14:39:39Z 2023-03-29T14:39:39Z 1995-11 https://hdl.handle.net/1721.1/149253 MIT-LCS-TM-541 application/pdf |
| spellingShingle | Russell, Alexander Sundaram, Ravi Symmetric Alternation Captures BPP |
| title | Symmetric Alternation Captures BPP |
| title_full | Symmetric Alternation Captures BPP |
| title_fullStr | Symmetric Alternation Captures BPP |
| title_full_unstemmed | Symmetric Alternation Captures BPP |
| title_short | Symmetric Alternation Captures BPP |
| title_sort | symmetric alternation captures bpp |
| url | https://hdl.handle.net/1721.1/149253 |
| work_keys_str_mv | AT russellalexander symmetricalternationcapturesbpp AT sundaramravi symmetricalternationcapturesbpp |