|
Abstract : |
Abstract. Phase transitions in constraint satisfaction problems (CSP's) are the subject of intense study. We identify a control parameter for random binary CSP's. There is a rapid transition in the probability of a CSP having a solution at a critical value of this parameter. This parameter allows different phase transition behaviour to be compared in an uniform manner, for example CSP's generated under different regimes. We then show that within classes, the scaling of behaviour can be modelled by a technique called "finite size scaling". This applies not only to probability of solubility, as has been observed before in other NP-problems, but also to search cost. Furthermore, the technique applies with equal validity to several different methods of varying problem size. As well as contributing to the understanding of phase transitions, we contribute by allowing much finer grained comparison of algorithms, and for accurate empirical extrapolations of behaviour., |
