[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.
http://cstheory.stackexchange.com/questions/16989/is-parity-p-contained-in-pp
Tim
More information about the FOM
mailing list