@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} }