On the phase transitions of random k-constraint satisfaction problems |
| |
Authors: | Yun Fan Jing Shen |
| |
Affiliation: | 1. Department of Mathematics, Central China Normal University, Wuhan, 430079, China;2. School of Science, Naval University of Engineering, Wuhan, 430033, China |
| |
Abstract: | Constraint satisfaction has received increasing attention over the years. Intense research has focused on solving all kinds of constraint satisfaction problems (CSPs). In this paper, first we propose a random CSP model, named k-CSP, that guarantees the existence of phase transitions under certain circumstances. The exact location of the phase transition is quantified and experimental results are provided to illustrate the performance of the proposed model. Second, we revise the model k-CSP to a random linear CSP by incorporating certain linear structure to constraint relations. We also prove the existence of the phase transition and exhibit its exact location for this random linear CSP model. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|