dc.contributor.author |
Buhrman, Harry |
dc.contributor.author |
Hermo Huguet, Montserrat |
dc.date |
1994-01-01 |
dc.identifier.citation |
Buhrman, H., Hermo, M. "On the sparse set conjecture for sets with low density". 1994. |
dc.identifier.uri |
http://hdl.handle.net/2117/97218 |
dc.language.iso |
eng |
dc.relation |
LSI-94-23-R |
dc.rights |
info:eu-repo/semantics/openAccess |
dc.rights |
http://creativecommons.org/licenses/by-nc-nd/3.0/es/ |
dc.subject |
Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica |
dc.subject |
Sparse set conjecture |
dc.subject |
Low density sets |
dc.title |
On the sparse set conjecture for sets with low density |
dc.type |
info:eu-repo/semantics/publishedVersion |
dc.type |
info:eu-repo/semantics/report |
dc.description.abstract |
We study the sparse set conjecture for sets with low density. The sparse set conjecture states that P = NP if and only if there exists a sparse Turing hard set for NP. In this paper we study a weaker variant of the conjecture. We are interested in the consequences of NP having Turing hard sets of density f(n), for (unbounded) functions f(n), that are sub-polynomial, for example log(n). We establish a connection between Turing hard sets for NP with density f(n) and bounded nondeterminism: We prove that if NP has a Turing hard set of density f(n), then satisfiability is computable in polynomial time with O(log(n)*f(n^c)) many nondeterministic bits for some constant c. As a consequence of the proof technique we obtain absolute results about the density of Turing hard sets for EXP. We show that no Turing hard set for EXP can have sub-polynomial density. On the other hand we show that these results are optimal w.r.t. relativizing computations. For unbounded functions f(n), there exists an oracle relative to which NP has a f(n) dense Turing hard tally set but still P is different from NP. |