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,

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

_{0}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 Σ_{2}, 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_{0}PP, which
itself is contained in PP. If A_{0}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^{A0PP} 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