Loading...
Loading...

Go to the content (press return)

Sparse sets, lowness, and highness

Author
Balcazar, J. L.; Book, R.; Schoening, U.
Type of activity
Journal article
Journal
SIAM journal on computing
Date of publication
1986-08
Volume
15
Number
1
First page
739
Last page
747
DOI
https://doi.org/10.1137/0215053 Open in new window
Repository
http://hdl.handle.net/2117/103245 Open in new window
URL
http://epubs.siam.org/doi/abs/10.1137/0215053 Open in new window
Abstract
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...
Citation
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.
Keywords
Discrete mathematics, Extended highness, Generalized highness Extended lowness, Generalized lowness, Polynomial-time hierarchy, Sparse sets
Group of research
LARCA - Laboratory of Relational Algorithmics, Complexity and Learnability

Participants

Attachments