Perceptrons, PP, and the polynomial hierarchy
Richard Beigel · 2003
The author constructs a predicate that is computable by a perceptron with linear size, order one, and exponential weights, but which cannot be computed by any perceptron having subexponential size, subpolynomial order, and subexponential weights. A consequence is that there is an oracle relative to which P/sup NP/ is not contained in PP.>