Portal de Periódicos da CAPES

Some Observations on Separating Complexity Classes

1991; Society for Industrial and Applied Mathematics; Volume: 20; Issue: 2 Linguagem: Inglês

10.1137/0220015

1095-7111

Ronald V. Book,

Optimization and Search Problems

Cai [J. Comput. System Sci., 38 (1989), pp. 68–85] proved that for almost every set A, ${\operatorname{PH}}(A) \ne {\operatorname{PSPACE}}(A)$. For every set A, there is a restricted relativization of the class ${\operatorname{PSPACE}}(A)$, denoted ${\operatorname{PQH}}(A)$, with the property that ${\operatorname{PQH}}(A)$ lies between ${\operatorname{PH}}(A)$ and ${\operatorname{PSPACE}}(A)$ (as was previously studied in [Theoret. Comput. Sci., 15 (1981), pp. 41–50] and [Theoret. Comput. Sci., 40 (1985), pp. 237–243]). It is shown here that ${\operatorname{PH}} \ne {\operatorname{PSPACE}}$ if and only if, for almost every set A, ${\operatorname{PH}}(A) \ne {\operatorname{PQH}}(A)$. Cai’s proof shows that for almost every set A, ${\operatorname{PQH}}(A) \ne {\operatorname{PSPACE}}(A)$, so that for almost every set A, ${\operatorname{PQH}}(A)$ bounds ${\operatorname{PSPACE}}(A)$ away from ${\operatorname{PH}}(A)$. Bennett and Gill [SIAM J. Comput., 10 (1981), pp.96–113] proved that for almost every set A, ${\operatorname{P}}(A) \ne {\operatorname{NP}}(A)$. For every set A, there is a restricted relativization of the class ${\operatorname{NP}}(A)$ (previously studied in [SIAM J Comput., 13 (1984), pp. 461–487]), denoted ${\operatorname{NP}}_{\text{B}}(A)$, with the property that ${\operatorname{NP}}_{\text{B}}(A)$ lies between ${\operatorname{P}}(A)$ and ${\operatorname{NP}}(A)$. It is known [SIAM J. Comput., 13(1984), pp. 461–487] that ${\operatorname{P}} \ne {\operatorname{NP}}$ if and only if there exists a set A such that ${\operatorname{P}}(A) \ne {\operatorname{NP}}_{\text{B}} (A)$. It is shown here that ${\operatorname{BPP}} \ne {\operatorname{AM}}$ if and only if for almost every set A, ${\operatorname{P}}(A) \ne {\operatorname{NP}}_{\text{B}} (A)$. A result of Kurtz [Inform. and Control, 57 (1983), pp. 40–47] is used to show that for almost every set A, ${\operatorname{NP}}_{\text{B}}(A)$ bounds ${\operatorname{NP}}(A)$ away from ${\operatorname{P}}(A)$. In addition, it is shown that membership in ${\operatorname{PSPACE}}$ can be characterized in terms of the ${\operatorname{PQH}}(\,)$-operator and membership in ${\operatorname{AM}}$ can be characterized in terms of the ${\operatorname{NP}}_{\text{B}} (\, )$-operator. Other results involving quantitative restrictions on access to information from oracles and qualitative restrictions on the use of such information are presented.