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
Repository Citation
Green, Frederic, "An oracle separating ΘP from PPPH" (1991). Computer Science. 76.
https://commons.clarku.edu/faculty_computer_sciences/76
APA Citation
Green, F. (1991). An oracle separating ΘP from PPPH. Information Processing Letters, 37(3), 149-153.