1995 | ReviewPaper | Chapter
On the sparse set conjecture for sets with low density
Authors : Harry Buhrman, Montserrat Hermo
Published in: STACS 95
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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(nc)) 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≠NP.