Title :
An oracle separating ⊕P from PPPH
Author_Institution :
Dept. of Math. & Comput. Sci., Clark Univ., Worcester, MA, USA
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: 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
Keywords :
Turing machines; computational complexity; ANDs; ORs; Turing machines; circuit complexity; constant depth circuit; exponential size; parity; separation; threshold gate; Circuits; Complexity theory; Computer science; Costs; Mathematics; Polynomials; Turing machines;
Conference_Titel :
Structure in Complexity Theory Conference, 1990, Proceedings., Fifth Annual
Conference_Location :
Barcelona
Print_ISBN :
0-8186-6072-4
DOI :
10.1109/SCT.1990.113977
