Phase Transition And Approximate Algorithm For#CSP

Phase transition becomes a hot research topic in recent year. Phase transition ofNP-Complete problem can help us to understand the nature of the hardness of the problem, sowe can use these information to improve the algorithms. With the increasing of someparticular parameter in the problem, some properties change from one state to another statesuddenly. For example, the SAT problem, it changes from almost all SAT to nearly allUNSAT with the increasing of r, which is the ratio of the number of clauses and the numberof variables. To my best of our knowledge, except k=2, no one has proved that the phasetransition of random SAT is exact other than the upper and lower bound of the exact point.Constraint satisfaction problem (CSP) is the general form of SAT, there are many workabout the phase transition of CSP from both experimental and theoretical. Xu and Li give anew model called RB Model to generate CSP instances, they prove not only the preciselocation of phase transition but also the instances following RB Model are hard to solve.The occurrence of phase transition exist not only in NP-Complete or NP-hard problem,but also in the problem whose complex is harder, such as QSAT and planning. The modelcounting of combinatorial problems have received much interest recently. The modelcounting of SAT and CSP is#P-Complete, just like conformant planning problem andprobabilistic inference problems. Bailey prove phase transition exist in the model countingof SAT problem by the first time. We following this line, we prove the decision version ofCSP has phase transition and the critical point is located. The problem is#CSP(dn/t): givea CSP instance, whether there is at least dn/tsatisfying assignment.Another research direction of model counting is the algorithm. Birnbaum give the firstsolver-CDP to solve#SAT, which extends from classic algorithm DP. Then the algorithm isimproved by the clause learning and component caching. The determination algorithmexpend too much time to find an answer, the approximate algorithm like Approx-count,Sample-count and Sample-Minisat can make it. Gomes involve XOR constraint toapproximate the number of satisfying assignment of CSP. In this paper, we give a newapproximate method to#CSP. We prove that the algorithm can solve a#CSP in polynomialtime, moreover, with the problem size increase, the accuracy become better and better.