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.