Collaborating Authors

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

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.

Beyond NP: the QSAT phase transition

AAAI Conferences

Ian P. Gent and Toby Walsh * Department of Computer Science University of Strathclyde Glasgow G1 1XL United Kingdom ipg@cs, strath,, twOcs, strath, Abstract We show that phase transition behavior similar to that observed in NPcomplete problems like random 3-SAT occurs further up the polynomial hierarchy in problems like random 2-QSAT. The differences between QSAT and SAT in phase transition behavior that Cadoli et al report are largely due to the presence of trivially unsatisfiable problems. Once they are removed, we see behavior more familiar from SAT and other NPcomplete domains. There are, however, some differences. Problems with short clauses show a large gap between worst case behavior and median, and the easy-hard-easy pattern is restricted to higher percentiles of search cost. We compute the "constralnedness" of k-QSAT problems for any k, and use this to predict the location of phase transitions.

Exact Phase Transitions in Random Constraint Satisfaction Problems

Journal of Artificial Intelligence Research

In this paper we propose a new type of random CSP model, called Model RB, which is a revision to the standard Model B. It is proved that phase transitions from a region where almost all problems are satisfiable to a region where almost all problems are unsatisfiable do exist for Model RB as the number of variables approaches infinity. Moreover, the critical values at which the phase transitions occur are also known exactly. By relating the hardness of Model RB to Model B, it is shown that there exist a lot of hard instances in Model RB.


AAAI Conferences

In a previous paper we defined the "deep structure" of a constraint satisfaction problem to be that set system produced by collecting the nogood ground instances of each constraint and keeping only those that are not supersets of any other. We then showed how to use such deep structure to predict where, in a space of problem instances, an abrupt transition in computational cost is to be expected. This paper explains how to augment this model with enough extra details to make more accurate estimates of the location of these phase transitions. We also show that the phase transition phenomenon exists for a much wider class of search algorithms than had hitherto been thought and explain theoretically why this is the case.

Phase Transitions in Classical Planning: an Experimental Study

AAAI Conferences

Phase transitions in the solubility of problem instances are known in many types of computational problems relevant for artificial intelligence, most notably for the satisfiability problem of the classical propositional logic. However, phase transitions in classical planning have received far less attention. Bylander has investigated phase transitions theoretically as well as experimentally by using simplified planning algorithms, and shown that most of the soluble problems can be solved by a naïve hill-climbing algorithm. Because of the simplicity of his algorithms he did not investigate hard problems on the phase transition region. In this paper, we address exactly this problem. We introduce two new models of problem instances, one eliminating the most trivially insoluble instances from Bylander's model, and the other restricting the class of problem instances further. Then we perform experiments on the behavior of different types of planning algorithms on hard problems from the phase transition region, showing that a planner based on general-purpose satisfiability algorithms outperforms two planners based on heuristic local search.