A New Upper Bound For#CSP Problem

Many problems in Artificial Intelligence are hard to solve, just like propositional satisfiability problem (SAT for short) and constraint satisfaction problem (CSP for short). To best of our knowledge, no one have proved that P=NP or NP=#P, so there are no polynomial time algorithms to solve SAT or CSP. The complexity of model counting of SAT and CSP is expotional time in O(a"). If we can improve the bound even a little to O((α-ε)n), no matter how little ε is. This little improvement may help us to solve a problem more than sever times.One of our contributions is to present an algorithm to solve the model counting of CSP. The main idea is to convert the CSP to2SAT instances. The solver to solve#2SAT is more generally although the problem is#P-complete either. We promote two ways to encode CSP to SAT, which are very simple and easy to understand. The example and experiments make us believe that our encoding ways are right, so the models before and after the encoding are the same.We give an upper bound for#CSP with m and q as the parameter, which is the number of constraints and the number of consist assignments for each constraint. As we known, this is the first time using parameters other than number of variables and domain of variables. There are other factors to influence the hardness of a problem exclude n and d, as m and q. The algorithm consist two parts, which depend on the number of tuples of satisfying assignment for each constraint is odd or even. When the number is even, we have O(φm*(2/q)m), φm is the best upper bound for#2-SAT, q is the number of satisfying tuples for each constraint. When q is odd, we have O(φm*((q2+q+2)IA)m/2) if q=4*k+1, and O(φm*((q2+q)/4)m/2) if q=4*k+3...