New Lower Bound of Critical Function for (k, s)-SAT
Year: 2006
Journal of Information and Computing Science, Vol. 1 (2006), Iss. 1 : pp. 3–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
Journal Article Details
Publisher Name: Global Science Press
Language: English
DOI: https://doi.org/2024-JICS-22854
Journal of Information and Computing Science, Vol. 1 (2006), Iss. 1 : pp. 3–10
Published online: 2006-01
AMS Subject Headings:
Copyright: COPYRIGHT: © Global Science Press
Pages: 8