Symmetric alternation captures BPP | Zendy

Alexander Russell | Zendy; Ravi Sundaram | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Symmetric alternation captures BPP

Author(s) -

Alexander Russell,

Ravi Sundaram

Publication year - 1998

Publication title -

computational complexity

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.973

H-Index - 39

eISSN - 1420-8954

pISSN - 1016-3328

DOI - 10.1007/s000370050007

Subject(s) - alternation (linguistics) , combinatorics , sigma , mathematics , hierarchy , oracle , class (philosophy) , discrete mathematics , time complexity , computer science , physics , philosophy , linguistics , software engineering , quantum mechanics , artificial intelligence , economics , market economy

We introduce the natural class containing those languages which may be expressed in terms of two symmetric quantifiers. The 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. We show that MA (and hence BPP) lies within , improving the constructions of [8, 6] (which show that BPP ). Symmetric alternation is shown to enjoy two strong structural properties which are used to prove the desired containment results.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research