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,

- 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]}.

--

Posted by Lance Fortnow to My Computational Complexity Web Log at 4/23/2003 7:40:25 AM

Powered by Blogger Pro