【作者】 龚平； 肖华； 许道云；

【Author】 GONG Ping XIAO Hua XU Daoyun

【机构】 贵州大学计算机科学系；

【摘要】 <正> (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(k>3). 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 dificult to determine the upper bounds of f(k) for larger.In this paper, a tree rule is introduced by reducing the steps of calculating stairways, and a deterministic calculation for stairways is presented to get the upper bounds for f(k)(k≥3). The deterministic algorithm is practical, and the upper bounds are near the bounds S. Hoory and S. Sezider got.更多还原

【Abstract】 (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(k>3). 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 dificult to determine the upper bounds of f(k) for larger.In this paper, a tree rule is introduced by reducing the steps of calculating stairways, and a deterministic calculation for stairways is presented to get the upper bounds for f(k)(k≥3). The deterministic algorithm is practical, and the upper bounds are near the bounds S. Hoory and S. Sezider got.更多还原