2026-04-17T01:19:44Zhttps://recercat.cat/oai/request

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

00925njm 22002777a 4500 dc Buhrman, Harry author Hermo Huguet, Montserrat author 1994-01-01 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) Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica Sparse set conjecture Low density sets On the sparse set conjecture for sets with low density