Computer Science

An oracle separating ΘP from PPPH

Document Type

Article

Abstract

We prove the existence of an oracle A such that ΘPA is not contained in PPPHA. 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. © 1991.

Publication Title

Information Processing Letters

Publication Date

1991

Volume

37

Issue

3

First Page

149

Last Page

153

ISSN

0020-0190

DOI

10.1016/0020-0190(91)90035-G

Keywords

Computational complexity, polynomial-time hierarchy, probabilistic polynomial time, relativized complexity class, threshold circuits

APA Citation

Green, F. (1991). An oracle separating ΘP from PPPH. Information Processing Letters, 37(3), 149-153.

Share

COinS