Computer Science
An oracle separating ⊕P from PPPH
Abstract
The existence of an oracle A such that ⊕PA is not contained in PPPHA is proved. This separation follows in a straightforward manner from a circuit complexity result, which is also proved here: to compute the parity of n inputs, any constant depth circuit consisting of a single threshold gate on top of ANDs and ORs requires exponential size in n.
This paper has been withdrawn.