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 \u00a0k distinct literals and every variable occurs at most s times. It is known that there exits an exponential \nis already NP-\nfunction \u00a0f such that for\ncomplete (\nare only known \n3\nk = , \u00a0and \u00a0it(cid:146)s \u00a0open \u00a0whether\nk = \u00a0and \nfor\nis \u00a0computable. \u00a0The \u00a0best \u00a0known \u00a0lower \u00a0and \u00a0upper \u00a0bounds \n3\n\u2126\n\u2212 \u2248\non ( )\n, \u00a0respectively. \u00a0In \u00a0this \u00a0paper, \u00a0analogous \u00a0to \u00a0the \n, \u00a0where\nf k \u00a0are \nrandomized \u00a0algorithm \u00a0for \u00a0finding \u00a0two \u00a0coloring \u00a0of \u00a0k \u2212 uniform \u00a0hypergraph, \u00a0we \u00a0first \u00a0present \u00a0a \u00a0similar \nrandomize \u00a0algorithm \u00a0for \u00a0outputting \u00a0an \u00a0assignment \u00a0for \u00a0a \u00a0given \u00a0formula. \u00a0Based \u00a0on \u00a0it \u00a0and \u00a0by \u00a0probabilistic \n"