2026-04-18T01:07:27Zhttps://recercat.cat/oai/request

oai:recercat.cat:2117/972182025-07-17T10:57:14Zcom_2072_1033col_2072_452950

On the sparse set conjecture for sets with low density Buhrman, Harry Hermo Huguet, Montserrat Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica Sparse set conjecture Low density sets 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. Postprint (published version) 1994-01-01 External research report Buhrman, H., Hermo, M. "On the sparse set conjecture for sets with low density". 1994. https://hdl.handle.net/2117/97218 eng LSI-94-23-R http://creativecommons.org/licenses/by-nc-nd/3.0/es/ Open Access 10 p. application/pdf