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 - 2024
DA - 2024/01
SN - 1
DO - http://doi.org/
UR - https://global-sci.org/intro/article_detail/jics/22854.html
KW -  ( , )k s

AB -  ( , )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