An Oracle Separating +P From PP ph .
Frederic Green · Structure in Complexity Theory Annual Conference · 1990
Abstract We prove the existence of an oracle A such that ΘP A is not contained in PP PH A . 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 and's and or's requires exponential size in n .