科研之友
微信
新浪微博
Facebook
分享链接
摘要
We consider random instances of constraint satisfaction problems (CSPs) where each variable has domain size O(1), each constraint is on O(1) variables, and the constraints are chosen from a specified distribution. The number of constraints is cn, where c is a constant. We prove that for every possible distribution, either the resolution complexity is almost surely polylogarithmic for sufficiently large c, or it is almost surely exponential for every c > 0. We characterize the distributions of each type. To do so, we introduce a closure operation on constraint sets which yields the set of all constraints that, in some sense, appear implicitly in the random CSP.
- 出版日期2013
