A lower bound for perceptrons and an oracle separation of the \(PP^{PH}\) hierarchy (Q1271610)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A lower bound for perceptrons and an oracle separation of the \(PP^{PH}\) hierarchy |
scientific article |
Statements
A lower bound for perceptrons and an oracle separation of the \(PP^{PH}\) hierarchy (English)
0 references
25 March 1999
0 references
A perception is a circuit with a single threshold gate, whose inputs are the outputs of boolean circuits with AND, OR, and NOT gates at the top, called the perceptron's subcircuits. The author shows that there are functions computable by linear size boolean circuits of depth \(k\) that require superpolynomial size perceptrons of depth \(k- 1,\) for \(k<\log n/(6 \log \log n)\) and exponential size perceptrons for constant \(k.\) The key to making the proof work is to use a separation between polynomial size depth-2 perceptrons with bounded fan-in and general polynomial size depth-2 perceptrons as the basis for the induction. This result implies the existence of an oracle \(A\) such that \(\Sigma_k^{p, A}\nsubseteq \text{PP}^{\Sigma_{k-2}^{p,A}}\) and, in particular, this oracle separates the levels in the \(\text{PP}^{\text{PH}}\) hierarchy. Using the same ideas, it is shown a lower bound for another function, which makes it possible to get an oracle \(A\) such that \(\Delta_k^{p,A}\nsubseteq \text{PP}^{\Sigma_{k-2}^{p,A}}.\)
0 references
mathematical problems of computer architecture
0 references
perception
0 references
lower bound for perceptrons
0 references
oracle separation
0 references
polynomial time hierarchy
0 references
relativization
0 references
parity
0 references
boolean circuits
0 references
circuit complexity
0 references