Geodesic
Relativizable and nonrelativizable theorems in the polynomial theory of algorithms
Izvestiya. Mathematics , Tome 42 (1994) no. 2, pp. 261-298

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

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. 
@article{IM2_1994_42_2_a1,
     author = {N. K. Vereshchagin},
     title = {Relativizable and nonrelativizable theorems in the polynomial theory of algorithms},
     journal = {Izvestiya. Mathematics },
     pages = {261--298},
     publisher = {mathdoc},
     volume = {42},
     number = {2},
     year = {1994},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/IM2_1994_42_2_a1/}
}
TY  - JOUR
AU  - N. K. Vereshchagin
TI  - Relativizable and nonrelativizable theorems in the polynomial theory of algorithms
JO  - Izvestiya. Mathematics 
PY  - 1994
SP  - 261
EP  - 298
VL  - 42
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IM2_1994_42_2_a1/
LA  - en
ID  - IM2_1994_42_2_a1
ER  - 
%0 Journal Article
%A N. K. Vereshchagin
%T Relativizable and nonrelativizable theorems in the polynomial theory of algorithms
%J Izvestiya. Mathematics 
%D 1994
%P 261-298
%V 42
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IM2_1994_42_2_a1/
%G en
%F IM2_1994_42_2_a1
N. K. Vereshchagin. Relativizable and nonrelativizable theorems in the polynomial theory of algorithms. Izvestiya. Mathematics , Tome 42 (1994) no. 2, pp. 261-298. http://geodesic.mathdoc.fr/item/IM2_1994_42_2_a1/