Title :
Lower bounds for perceptrons solving some separation problems and oracle separation of AM from PP
Author :
Vereshchagin, Nikolai K.
Author_Institution :
Dept. of Math. Logic, Moscow State Univ., Russia
Abstract :
We prove that perceptrons separating Boolean matrices in which each row has a one from matrices in which many rows have no one must have either large total weight or large order. This result extends one-in-a-box theorem by Minsky and Papert (1988) stating that perceptrons of small order cannot decide if each row of a given Boolean matrix has a one. As a consequence, we prove that AM∩co-AM⊄≠PP under some oracle. This contrasts the fact that MA⊆PP under any oracle
Keywords :
Boolean algebra; automata theory; matrix algebra; perceptrons; threshold logic; Boolean matrices; oracle; oracle separation; perceptrons; separation problems; Boolean functions; Circuits; Complexity theory; Cultural differences; Functional analysis; Linear programming; Polynomials; Turing machines; Upper bound;
Conference_Titel :
Theory of Computing and Systems, 1995. Proceedings., Third Israel Symposium on the
Conference_Location :
Tel Aviv
Print_ISBN :
0-8186-6915-2
DOI :
10.1109/ISTCS.1995.377047
