Geodesic
Oracle separation of complexity classes and lower bounds for perceptrons solving separation problems
Izvestiya. Mathematics , Tome 59 (1995) no. 6, pp. 1103-1122

Voir la notice de l'article provenant de la source Math-Net.Ru

In the first part of the paper we prove that, relative to a random oracle, the class NP contains infinite sets having no infinite Co-NP-subsets (Co-NP-immune sets). In the second part we prove that perceptrons separating Boolean matrices in which each row contains at least one 1 from matrices in which many rows (say 99% of them) have no 1's must have either large size or large order. This result partially strengthens the “one-in-a-box” theorem of Minsky and Papert [16] which states that perceptrons of small order cannot decide if every row of a given Boolean matrix has a 1. As a corollary, we prove that $\text{AM}\cap\text{Co-AM}\not\subseteq\text{PP}$ under some oracles. 
@article{IM2_1995_59_6_a0,
     author = {N. K. Vereshchagin},
     title = {Oracle separation of complexity classes and lower bounds for perceptrons solving separation problems},
     journal = {Izvestiya. Mathematics },
     pages = {1103--1122},
     publisher = {mathdoc},
     volume = {59},
     number = {6},
     year = {1995},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/IM2_1995_59_6_a0/}
}
TY  - JOUR
AU  - N. K. Vereshchagin
TI  - Oracle separation of complexity classes and lower bounds for perceptrons solving separation problems
JO  - Izvestiya. Mathematics 
PY  - 1995
SP  - 1103
EP  - 1122
VL  - 59
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IM2_1995_59_6_a0/
LA  - en
ID  - IM2_1995_59_6_a0
ER  - 
%0 Journal Article
%A N. K. Vereshchagin
%T Oracle separation of complexity classes and lower bounds for perceptrons solving separation problems
%J Izvestiya. Mathematics 
%D 1995
%P 1103-1122
%V 59
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IM2_1995_59_6_a0/
%G en
%F IM2_1995_59_6_a0
N. K. Vereshchagin. Oracle separation of complexity classes and lower bounds for perceptrons solving separation problems. Izvestiya. Mathematics , Tome 59 (1995) no. 6, pp. 1103-1122. http://geodesic.mathdoc.fr/item/IM2_1995_59_6_a0/