This article is cited in 20 papers

Relativizable and nonrelativizable theorems in the polynomial theory of algorithms

N. K. Vereshchagin

Institute of New Technologies

Abstract: 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.

UDC: 510.52

MSC: 68Q15

Received: 16.03.1990
Revised: 18.11.1991

 English version: Russian Academy of Sciences. Izvestiya Mathematics, 1994, 42:2, 261–298

Bibliographic databases:

• 
• 
• 
•