@Article{JICS-1-03,
author = {},
title = {New Lower Bound of Critical Function for (k, s)-SAT},
journal = {Journal of Information and Computing Science},
year = {2006},
volume = {1},
number = {1},
pages = {03--10},
abstract = { ( , )k s
 is the propositional satisfiable problem restricted to instances where each clause has 
exactly  k distinct literals and every variable occurs at most s times. It is known that there exits an exponential 
is already NP-
function  f such that for
complete (
are only known 
3
k = ,  and  it(cid:146)s  open  whether
k =  and 
for
is  computable.  The  best  known  lower  and  upper  bounds 
3
Ω
− ≈
on ( )
,  respectively.  In  this  paper,  analogous  to  the 
,  where
f k  are 
randomized  algorithm  for  finding  two  coloring  of  k − uniform  hypergraph,  we  first  present  a  similar 
randomize  algorithm  for  outputting  an  assignment  for  a  given  formula.  Based  on  it  and  by  probabilistic 
},
issn = {3080-180X},
doi = {https://doi.org/},
url = {http://global-sci.org/intro/article_detail/jics/22854.html}
}