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 |
| Summary: | 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. |
|---|