Wednesday, April 23, 2003

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 A0PP 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 BPPpath but there is a relativized world where it is not contained in Σ2, giving a relativized answer to the open question in my CCW on BPPpath. 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 A0PP, which itself is contained in PP. If A0PP = 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 SPPC=P and he shows that SPPA0PP 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].

No comments:

Post a Comment