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
    0 references
    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

    Identifiers