New Lower Bound of Critical Function for (k, s)-SAT

Abstract

" ( , )k s\n is the propositional satisfiable problem restricted to instances where each clause has \nexactly k distinct literals and every variable occurs at most s times. It is known that there exits an exponential \nis already NP-\nfunction f such that for\ncomplete (\nare only known \n3\nk = , and it(cid:146)s open whether\nk = and \nfor\nis computable. The best known lower and upper bounds \n3\nΩ\n- ≈\non ( )\n, respectively. In this paper, analogous to the \n, where\nf k are \nrandomized algorithm for finding two coloring of k - uniform hypergraph, we first present a similar \nrandomize algorithm for outputting an assignment for a given formula. Based on it and by probabilistic \n"