Title: Perceptrons, PP, and the Polynomial Hierarchy

Authors: Richard Beigel

Abstract: We construct a predicate that is computable by a perceptron with linear size, order 1, and exponential weights, but which cannot be computed by any perceptron having subexponential (2no(1)) size, subpolynomial (no(1)) order and subexponential weights. A consequence is that there is an oracle relative to which PNP is not contained in PP.

Download Full Paper