Classes of Simplified NP-complete Instances
Ping Gong · Journal of Guizhou University · 2005
(k,s)-SAT is the propositional satisfiable problem restricted to instances where each clause has exactly k distinct literal and every variable occurs at most s times. It is known that there exits an exponential 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(k3). Exact values of f are only known for k=3 and k=4, and it's open whether f is computable. In [2], S. Hoory and S. Sezider obtain a computable upper bound function for f(k)(k≥3) . The approach is to create some instance in (k,s)-SAT by calculation stairways, which are corresponded to constructing some formulas in MU(1). However, the calculation for stairways is nondeterministic. It is difficult to determine the upper bounds of f(k) for larger k. In this paper, a tree rule is introduced by reducing the steps of calculating stairways, and a deterministic calculation for f(k)(k≥3). The deterministic algorithm is practical, and the upper bounds are near the bounds S. Hoory and S. Sezider got.