2011/02/24 by Minghao Yin, Ping Huang, Yin, Minghao +1
Computer Science · #Advanced Database Systems and Queries #Artificial Intelligence (cs.AI) #Computational Complexity (cs.CC) #Constraint Satisfaction and Optimization #Data Management and Algorithms #FOS: Computer and information sciences #cs.AI #cs.CC
paper · pdf · doi:10.48550/arxiv.1102.4922
submitted to AAAI-11
arxiv created 2011/02/24 · openalex publication_date 2011/02/24 · arxiv updated 2011/02/25 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
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.