Relativizable and nonrelativizable theorems in the polynomial theory of algorithms

N. K. Vereshchagin

Izvestiya. Mathematics , Tome 42 (1994) no. 2, pp. 261-298.

Résumé

Starting with the paper of Baker, Gill, and Solovay [BGS 75] in complexity theory, many results have been proved that separate certain relativized complexity classes or show that they have no complete language. All results of this kind were, in fact, based on lower bounds for Boolean decision trees of a certain type or for machines with polylogarithmic restrictions on time. The following question arises: Are these methods of proving “relativized” results universal? In the first part of the present paper a general framework is proposed in which assertions of universality of this kind may be formulated and proved as convenient criteria. Using these criteria we obtain, as easy consequences of the known results on Boolean decision trees, some new “relativized” results and new proofs of some known results. In the second part of the paper, these general criteria are applied to many particular cases. For example, for many of the complexity classes studied in the literature all relativizable inclusions between the classes are found.

Bibliographie

[1] Ajtai N., “$\Sigma_1^1$-formulae on finite structures”, Ann. Pure Appl. Logic, 24 (1983), 1–48 | DOI | MR | Zbl

[2] Aiello W., Goldwasser S., Hastad J., “On the Power of Interaction”, 26th FOCS, 1986, 368–379

[3] Ambos-Spies K., “A Note on Complete Problems for Complexity Classes”, Inf. Proc. Lett., 23 (1986), 227–230 | DOI | MR | Zbl

[4] Babai L., “Trading Group Theory for Randomness”, 17th STOC, 1985, 421–429

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

[6] Baker T., Gill J., Solovay R., “Relativizatioh of $\langle\langle\operatorname{P}=?\operatorname{NP} \rangle\rangle$ Question”, SIAM J. on Computing, 1975, 431–442 | DOI | MR | Zbl

[7] Cai J., Hemachandra L., “On the Power of Parity Polynomial Time”, Mathem. Systems Theory, 23:2 (1990), 95–106 | DOI | MR | Zbl

[8] Fortnow L., Sipser M., “Are There Interactive Protocols for $\operatorname{co-NP}$ Languages?”, Inf. Proc. Lett., 28 (1988), 249–251 | DOI | MR | Zbl

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

[10] Gurevich Y., “Algebras of Feasible Functions”, 24th FOCS, 1983, 210–214

[11] Goldwasser S., Micali S., Rackoff C., “The Knowledge Complexity of Interactive Proof Systems”, SIAM J. on Computing, 18 (1989), 186–208 | DOI | MR | Zbl

[12] Goldwasser S., Sipser M., “Private Coins Versus Public Coins in Interactive Proof Systems”, 18th STOC, 1986, 59–68

[13] Hastad J., “Almost Optimal lower bounds for small depth circuits”, 18th STOC, 1986, 6–20

[14] Ilartmanis J., Immerman N., “On complete problems for $\operatorname{NP}\cap\operatorname{co-NP}$”, ICALP 85, Lect. Notes Comp. Sci., 194, 1985, 250–259 | MR

[15] Hemachandra L., Jain S., Vereshchagin N., “Banishing Robust Turing Completeness”, Logical foundations of computer science (Tver', 1992), Lecture Notes in Comput. Sci., 620, Springer, Berlin, 1992, 186–197 | MR | Zbl

[16] Köbler J., Johannes U., Toda S., Torán J., “Turing machines with few accepting computations and low sets for PP”, Structure in Complexity Theory, 1989 | Zbl

[17] Lund C., Fortnow L., Karloff H., Nisan N., “The Polynomial Time Hierarchy has Interactive Proofs”, Proc. 31th FOCS, 1990, 2–10 | MR

[18] Minsky M., Papert S., Perceptrons, MTT Press, Cambridge, MA, 1988, Vtoroe izdanie (pervoe izdanie poyavilos v 1968 g.)

[19] Nisan N., “Probabilistic versus Deterministic Decision Trees and CREW PRAM Complexity”, Proc. 21th STOC, 1989, 327–335

[20] Santha M., “Relativized Arthur–Merlin versus Merlin–Arthur Games”, Inform. and Comput, 80 (1989), 44–49 | DOI | MR | Zbl

[21] Shamir A., “IP=PSPACE”, 31st Annual Symposium on Foundations of Computer Science, Vol. I, II (St. Louis, MO, 1990), IEEE Comput. Soc. Press, Los Alamitos, CA, 1990, 11–15 | MR

[22] Sipser M., “On Relativizations and the Existence of Complete Sets”, Automata, languages and programming, Lecture Notes in Comput. Sci., 140, Springer, Berlin, 1982, 523–531 | MR

[23] Sipser M., “A complexity Theoretic Approach for Randomness”, 15th STOC, 1983, 330–335

[24] Vereshchagin N. K., “On the Power of PP”, Proc. 7th Conf. on Structure in Complexity Theory, 1992, 138–143 | MR

[25] Yao A., “Separating the Polynomial Hierarchy by Oracles”, Proc. 26th FOCS, 1985, 1–10

[26] Toda S., “On the computational power of PP and OP”, Proc. 30th FOCS, 1989, 514–519

[27] Hartmanis J., Hemachandra L., “Complexity classes without machines: On complete languages for UP”, Automata, languages and programming, Lect. Notes in Comp. Sci., 226, Springer, Berlin, 123–135 ; Theor. Comp. Sci., 58 (1988) | MR | DOI | MR | Zbl