A new lower bound of critical function for (k,s)-SAT

(k, s)-SAT is the propositional satisfiable problem restricted to the instance where each clause has exactly k distinct literals and every variable occurs at most s times. It is known that there exits a critical function f such that for s ≤ f(k), all (k, s)-SAT instances are satisfiable, but (k, f(k) + 1)-SAT is already NP-complete(k ≥3). It's open whether f is computable. In this paper, analogous to the randomized algorithm for finding a two-coloring for given uniform k-hypergraph, tlie similar one for outputting an assignment for a given formula is presented. Based on it and the probabilistic method, we prove, for every integer k > 2, each formula F in (k, * )-CNF with less than 0.58 x √ k Ink 2k clauses is satisfiable. In addition, by the Lovasz Local Lemma, we improve the previous result about the lower bound of f(k).