Portal de Periódicos da CAPES

On bounded query machines

1985; Elsevier BV; Volume: 40; Linguagem: Inglês

10.1016/0304-3975(85)90168-9

1879-2294

José L. Balcázar, Ronald V. Book, Uwe Schöning,

Advanced Graph Theory Research

Simple proofs are given for each of the following results: (a) P = Pspace if and only if, for every set A, P(A) = Pquery(A) (Selman et al., 1983): (b) NP = Pspace if and only if, for every set A, NP(A) = NPquery(S) (Book, 1981); (c) PH = Pspace if and only if, for every set A, PH(A) = PQH(A) (Book and Wrathall, 1981); (c) PH = Pspace if and only if, for every set set S, PH(S) = PQH(S) = Pspace(S) (Balcázar et al., 1986; Long and Selman, 1986).