@Article{JICS-1-03, author = {}, title = {New Lower Bound of Critical Function for (k, s)-SAT}, journal = {Journal of Information and Computing Science}, year = {2024}, 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 = {1746-7659}, doi = {https://doi.org/}, url = {http://global-sci.org/intro/article_detail/jics/22854.html} }