Counting Solutions of Constraint Satisfiability Problems:Exact Phase Transitions and Approximate Algorithm

02/24/2011
by   Minghao Yin, et al.
0

The study of phase transition phenomenon of NP complete problems plays an important role in understanding the nature of hard problems. In this paper, we follow this line of research by considering the problem of counting solutions of Constraint Satisfaction Problems (#CSP). We consider the random model, i.e. RB model. We prove that phase transition of #CSP does exist as the number of variables approaches infinity and the critical values where phase transitions occur are precisely located. Preliminary experimental results also show that the critical point coincides with the theoretical derivation. Moreover, we propose an approximate algorithm to estimate the expectation value of the solutions number of a given CSP instance of RB model.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset