Some NP-complete Instances in (r,s)-SAT

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

【Author】 XIAO Hua GONG Ping XU Daoyun (Department of Computer Science,Guizhou University,Guiyang 550025)

【机构】 Department of Computer Science,Guizhou University,Guiyang 550025；

【摘要】 <正> It is known that(r, s)-SAT is solvable in polynomial time(r>0), there exists a critical function f such that for r≥3 all instances of (r,f(r))-SAT are satisfiable and (r,f(r) + 1)-SAT is NP-complete. However,it is open whether f is computable. In this paper, we construct some minimal unsatisfiable instances in rSAT by investigating the tree resolution proofs of minimal unsatisfiable formulas and the splitting on formulas. Further, we present some minimal unsatisfiable formulas for NP-completeness of some instances in (r,s)-SAT.更多还原

【Abstract】 It is known that(r, s)-SAT is solvable in polynomial time(r>0), there exists a critical function f such that for r≥3 all instances of (r,f(r))-SAT are satisfiable and (r,f(r) + 1)-SAT is NP-complete. However,it is open whether f is computable. In this paper, we construct some minimal unsatisfiable instances in rSAT by investigating the tree resolution proofs of minimal unsatisfiable formulas and the splitting on formulas. Further, we present some minimal unsatisfiable formulas for NP-completeness of some instances in (r,s)-SAT.更多还原