Complexity Classes of the Week: SBP and A0PP

Previous CCW

Two new complexity classes developed independently for two different purposes with eerily similar definitions. Let's take a look.

Böhler, Glaßer and Meister present a new class SBP that can be defined as follows. A language L is in SBP if there is a #P function f and an FP function g such that for all x,

1. if x is in L then f(x)>g(x), and
2. if x is not in L then 0≤f(x)<g(x)/2.

Vyalyi introduces a class A₀PP which has exactly the same definition except #P is replaced by Gap-P. [If I lose you in alphabet soup in this post, you can use the zoo to keep up.]

In both classes the "2" in the definition can be replaced by 2^|x|k for any fixed k.

SBP sits between MA and AM, a rare natural class between these two. SBP is also contained in BPP_path but there is a relativized world where it is not contained in Σ₂, giving a relativized answer to the open question in my CCW on BPP_path. SBP is closed under union but whether it is closed under intersection remains open even in relativized worlds.

QMA, the quantum version of MA, is contained in A₀PP, which itself is contained in PP. If A₀PP = PP then PH is in PP. He claims this gives evidence that QMA is not PP but given strong pseudorandom function, PH is in PP. But co-NP is probably not in QMA which is evidence enough for me that QMA is not equal to PP.

To prove his later result, Vyalyi notes that P^#P[1] is in SPP^C₌P and he shows that SPP^A₀PP is contained in PP and his result follows since C₌P is in PP and by Toda's Theorem PH is in P^#P[1].