A lower bound for perceptrons and an oracle separation of the PP/sup PH/ hierarchy

摘要

We show 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). This result implies the existence of an oracle A such that /spl Sigma//sub k//sup p,A//spl nsub/PP/sup /spl Sigma//(/sub k-2//sup p,A/) and in particular this oracle separates the levels in the PP/sup PH/ hierarchy. Using the same ideas, we show a lower bound for another function, which makes it possible to strengthen the oracle separation to /spl Delta//sub k//sup p,A//spl nsub/PP/sup /spl Sigma//(/sub k-2//sup p,A/).