[FOM] Counting classes

pax0 at seznam.cz pax0 at seznam.cz
Thu Mar 21 07:35:26 EDT 2013


A complexity theory question:
is parity-P subset of Maj-P?
NP *is* subset of Maj-P by the follwoing simple argument:
attach to each rejecting leaf the pair (accept , reject)
Then if there was an accepting path, we get membership in Maj-P.
Can we make similar modification to get
Parity-P is subset of maj-P/or this is not know to hold?
Thank you, Jan Pax
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20130321/32f45609/attachment.html>


More information about the FOM mailing list