Locating the phase transition in binary constraint satisfaction problems Export

@article{citeulike:2791681, abstract = {The phase transition in binary constraint satisfaction problems, i.e. the transition from a region in which almost all problems have many solutions to a region in which almost all problems have no solutions, as the constraints become tighter, is investigated by examining the behaviour of samples of randomly-generated problems. In contrast to theoretical work, which is concerned with the asymptotic behaviour of problems as the number of variables becomes larger, this paper is concerned with the location of the phase transition in finite problems. The accuracy of a prediction based on the expected number of solutions is discussed; it is shown that the variance of the number of solutions can be used to set bounds on the phase transition and to indicate the accuracy of the prediction. A class of sparse problems, for which the prediction is known to be inaccurate, is considered in detail; it is shown that, for these problems, the phase transition depends on the topology of the constraint graph as well as on the tightness of the constraints.}, author = {Smith, Barbara M. and Dyer, Martin E.}, booktitle = {Frontiers in Problem Solving: Phase Transitions and Complexity}, citeulike-article-id = {2791681}, citeulike-linkout-0 = {http://dx.doi.org/10.1016/0004-3702(95)00052-6}, citeulike-linkout-1 = {http://www.sciencedirect.com/science/article/B6TYF-3VSNHP6-8/1/956c83e9ede93ff77e151036a0932ede}, doi = {10.1016/0004-3702(95)00052-6}, journal = {Artificial Intelligence}, month = {March}, number = {1-2}, pages = {155--181}, posted-at = {2009-04-22 08:04:59}, priority = {2}, title = {Locating the phase transition in binary constraint satisfaction problems}, url = {http://dx.doi.org/10.1016/0004-3702(95)00052-6}, volume = {81}, year = {1996} }

TY - JOUR ID - citeulike:2791681 L3 - citeulike-article-id:2791681 N2 - The phase transition in binary constraint satisfaction problems, i.e. the transition from a region in which almost all problems have many solutions to a region in which almost all problems have no solutions, as the constraints become tighter, is investigated by examining the behaviour of samples of randomly-generated problems. In contrast to theoretical work, which is concerned with the asymptotic behaviour of problems as the number of variables becomes larger, this paper is concerned with the location of the phase transition in finite problems. The accuracy of a prediction based on the expected number of solutions is discussed; it is shown that the variance of the number of solutions can be used to set bounds on the phase transition and to indicate the accuracy of the prediction. A class of sparse problems, for which the prediction is known to be inaccurate, is considered in detail; it is shown that, for these problems, the phase transition depends on the topology of the constraint graph as well as on the tightness of the constraints. IS - 1-2 JF - Artificial Intelligence EP - 181 TI - Locating the phase transition in binary constraint satisfaction problems VL - 81 T2 - Frontiers in Problem Solving: Phase Transitions and Complexity SP - 155 AU - Smith, Barbara AU - Dyer, Martin PY - 1996/03// UR - http://dx.doi.org/10.1016/0004-3702(95)00052-6 ER -