Oracle separation of complexity classes and lower bounds for perceptrons solving separation problems

N. K. Vereshchagin

Izvestiya. Mathematics , Tome 59 (1995) no. 6, pp. 1103-1122.

Résumé

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.

Bibliographie

[1] Babai L., “Trading group theory for randomness”, 17th Annual ACM Symposium on Theory of Computing, 1985, 421–429

[2] Baker T., Gill J., Solovay R., “Relativization of $\mathrm{P}=?\mathrm{NP}$ question”, SIAM Journal on Computing, 4:4 (1975), 431–442 | DOI | MR | Zbl

[3] Beigel R., “Perceptrons, PP, and the polynomial time hierarchy”, 7th Annual Conference on Structure in Complexity Theory (July 1992), Boston, MA, 14–19 | MR

[4] Beigel R., Reingold N., Spielman D., “PP is closed under intersection”, 23th Annual ACM Symposium on Theory of Computing, 1991, 1–9

[5] Bennet C. H., Gill J., “Relative to a random oracle $\mathrm{P}\ne \mathrm{NP}\ne \mathrm{coNP}$ with probability 1”, SIAM Journal on Computing, 10 (1981), 96–113 | DOI | MR | Zbl

[6] Blum M., Impagliazzo R., “General oracle and oracle classes”, 28th Annual IEEE Symposium on Foundation of Computer Science (May 1987), New York, 118–126

[7] Chernoff H., “A measure of assymptotic efficiency for tests of a hypothesis based on the sum of observations”, Annals of Mathematical Statistics, 23 (1952), 493–509 | DOI | MR

[8] Ehlich H., Zeller K., “Schwankung von Polynomen zwischen Gitterpunkten”, Mathematische Zeitschrift, 86 (1964), 41–44 | DOI | MR | Zbl

[9] Fortnow L., Reingold N., “PP is closed under truth table reductions”, 6th Annual Conference on Structure in Complexity Theory, 1991, 13–15 | MR

[10] Fu B., Separating $\mathrm{PH}$ from PP by relativisation, Preprint, 1990

[11] Furst N., Saxe J., Sipser M., “Parity, circuits and the polynomial time hierarchy”, Mathematical Systems Theory, 17 (1984), 13–27 | DOI | MR | Zbl

[12] Kurtz S., Mahaney S., Royer J., “Average dependence and random oracle”, 7th Annual Conference on Structure in Complexity Theory (July 1992), Boston, MA, 306–317 | MR

[13] Toda S., “On the computational power of PP and $\oplus \mathrm{P}$”, 30th Annual IEEE Symposium on Foundation of Computer Science, 1989, 514–519; “PP is as hard as the polynomial time hierarchy”, SIAM Journal on Computing, 20 (1991), 865–877 | DOI | MR | Zbl

[14] Vereshchagin N. K., “On the power of PP”, 7th Conference on Structure in Complexity Theory, 1992, 138–143 | MR | Zbl

[15] Vereshchagin N. K., Lower bounds for perceptrons solving some separation problems and oracle separation of AM from PP, Technical Report 498, Computer Science Department, University of Rochester, 1994

[16] Vereshchagin N. K., “Lower bounds for perceptrons solving some separation problems and oracle separation of AM from PP”, 3rd Israel Symposium on Theory of Computing and Systems, 1995 | MR | Zbl

[17] Ashmanov S. A., Lineinoe programmirovanie, Nauka, M., 1981 | Zbl

[18] Vereschagin N. K., “Sootnoshenie NP- i Co-NP-mnozhestv otnositelno sluchainogo orakula”, Izv. VUZov. Seriya Matematika, 1993, no. 3, 31–39 ; Proc. of 8th Annual IEEE Conference on Structure in Complexity Theory (May 1993, San-Diego) | Zbl

[19] Minskii M., Peipert S., Perseptrony, Mir, M., 1973

[20] Polia G., Sege G., Zadachi i teoremy iz analiza, T. 2, Nauka, M., 1978

[21] Rozenkraft Dzh. M., Reifen A., Posledovatelnoe dekodirovanie, IL, M., 1963