[FOM] Counting classes

Timothy Y. Chow tchow at alum.mit.edu
Sun Mar 24 20:05:48 EDT 2013

Jan Pax asked:

> is parity-P subset of Maj-P?

I replied to Pax by private email but figured I might as well share the 
answer on FOM.

Maj-P is also known as PP.  The answer to the above question is not known. 
It is a straightforward exercise to show that P^(#P) = P^PP, from which it 
follows that P^(parity-P) is contained in P^PP.  This is evidence that 
parity-P is contained in PP.  However, it has been known since 1991 that 
there is an oracle A such that (parity-P)^A is not contained in PP^A.  I 
learned this by posting Pax's question to cstheory.stackexchange.



More information about the FOM mailing list