Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6417616 | Journal of Mathematical Analysis and Applications | 2016 | 11 Pages |
Abstract
Consider the model d-k-CSP which consists of a set of n variables with the domain size d, and a set of t=rnlnâ¡dâlnâ¡p constraints where each constraint binds k distinct variables and permits pdk tuples of values. We prove that the exact phase transition of the model d-k-CSP occurs at rc=1 as long as klnâ¡d=αlnâ¡n, where α satisfies that 12+12(2kâ1)+εâ¤Î±â¤1 (ε>0 is a sufficiently small constant). More importantly, we establish the finite-size scaling about this transition. Specifically, let δ>0 be a given constant, the probability of satisfiability of the model d-k-CSP is greater than 1âδ if râ¤1âÎ(1n1âνlnâ¡d) (ν is dependent on the control parameters) and is less than δ if râ¥1+Î(1nlnâ¡d).
Related Topics
Physical Sciences and Engineering
Mathematics
Analysis
Authors
Guangyan Zhou, Zongsheng Gao, Jun Liu,