Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Sparse sets, lowness, and highness

Autor
Balcazar, J. L.; Book, R.; Schoening, U.
Tipus d'activitat
Article en revista
Revista
SIAM journal on computing
Data de publicació
1986-08
Volum
15
Número
1
Pàgina inicial
739
Pàgina final
747
DOI
https://doi.org/10.1137/0215053 Obrir en finestra nova
Repositori
http://hdl.handle.net/2117/103245 Obrir en finestra nova
URL
http://epubs.siam.org/doi/abs/10.1137/0215053 Obrir en finestra nova
Resum
We develop the notions of “generalized lowness” for sets in PH (the union of the polynomial-time hierarchy) and of “generalized highness” for arbitrary sets. Also, we develop the notions of “extended lowness” and “extended highness” for arbitrary sets. These notions extend the decomposition of NP into low sets and high sets developed by Schöning [15] and studied by Ko and Schöning [9]. We show that either every sparse set in PH is generalized high or no sparse set in PH is gen...
Citació
Balcazar, J. L., Book, R., Schoening, U. Sparse sets, lowness, and highness. "SIAM journal on computing", Agost 1986, vol. 15, núm. 1, p. 739-747.
Paraules clau
Discrete mathematics, Extended highness, Generalized highness Extended lowness, Generalized lowness, Polynomial-time hierarchy, Sparse sets
Grup de recerca
LARCA - Laboratori d'Algorísmia Relacional, Complexitat i Aprenentatge

Participants

Arxius