Carregant...
Carregant...

Vés al contingut (premeu Retorn)

On bounded query machines

Autor
Balcazar, J. L.; Book, R.; Schoening, U.
Tipus d'activitat
Article en revista
Revista
Theoretical computer science
Data de publicació
1985-04
Volum
40
Número
1
Pàgina inicial
237
Pàgina final
243
DOI
https://doi.org/10.1016/0304-3975(85)90168-9 Obrir en finestra nova
URL
http://www.sciencedirect.com/science/article/pii/0304397585901689 Obrir en finestra nova
Resum
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).
Paraules clau
Query machines
Grup de recerca
LARCA - Laboratori d'Algorísmia Relacional, Complexitat i Aprenentatge

Participants