Paper Info
Title
On the Sparse Set Conjecture for Sets with Low Denisty
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 asparse Turing hard set for NP . In this paper we study a weaker variant ofthe conjecture. We are interested in the consequences of NP having Turinghard sets of density f(n), for (unbounded) functions f(n), that aresub-polynomial, for example log(n). We establish a connection betweenTuring hard sets for NP with density f(n) and bounded...
Year
DOI
Venue
1995
10.1007/3-540-59042-0_109
STACS
Keywords
Field
DocType
satisfiability,polynomial time
Cook–Levin theorem,Discrete mathematics,Combinatorics,Sparse language,NP-easy,Turing reduction,Turing,Alternating Turing machine,Mathematics,NP,Bounded function
Conference
Citations 
PageRank 
References 
2
0.39
16
Authors
2
Name
Order
Citations
PageRank
Harry Buhrman11607117.99
Montserrat Hermo25510.77