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: | , |
|---|---|
| יצא לאור: |
2023
|
| גישה מקוונת: | https://hdl.handle.net/1721.1/149253 |