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

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

2011-02-24

arxiv.org/abs/1102.4922v1

Computer Science

Artificial Intelligence

submitted to AAAI-11

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Counting Solutions of Constraint Satisfiability Problems:Exact Phase Transitions and Approximate Algorithm does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Counting Solutions of Constraint Satisfiability Problems:Exact Phase Transitions and Approximate Algorithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Counting Solutions of Constraint Satisfiability Problems:Exact Phase Transitions and Approximate Algorithm will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-86279