TY - JOUR
T1 - New Lower Bound of Critical Function for (k, s)-SAT
AU - 
JO - Journal of Information and Computing Science
VL - 1
SP - 03
EP - 10
PY - 2006
DA - 2006/02
SN - 1
DO - http://doi.org/
UR - https://global-sci.org/intro/article_detail/jics/22854.html
KW - 
AB -  ( , )k s
 is the propositional satisfiable problem restricted to instances where each clause has 
exactly &nbsp;k distinct literals and every variable occurs at most s times. It is known that there exits an exponential 
is already NP-
function &nbsp;f such that for
complete (
are only known 
3
k = , &nbsp;and &nbsp;it(cid:146)s &nbsp;open &nbsp;whether
k = &nbsp;and 
for
is &nbsp;computable. &nbsp;The &nbsp;best &nbsp;known &nbsp;lower &nbsp;and &nbsp;upper &nbsp;bounds 
3
Ω
− ≈
on ( )
, &nbsp;respectively. &nbsp;In &nbsp;this &nbsp;paper, &nbsp;analogous &nbsp;to &nbsp;the 
, &nbsp;where
f k &nbsp;are 
randomized &nbsp;algorithm &nbsp;for &nbsp;finding &nbsp;two &nbsp;coloring &nbsp;of &nbsp;k − uniform &nbsp;hypergraph, &nbsp;we &nbsp;first &nbsp;present &nbsp;a &nbsp;similar 
randomize &nbsp;algorithm &nbsp;for &nbsp;outputting &nbsp;an &nbsp;assignment &nbsp;for &nbsp;a &nbsp;given &nbsp;formula. &nbsp;Based &nbsp;on &nbsp;it &nbsp;and &nbsp;by &nbsp;probabilistic