On the constraint length of random $$k$$k-CSP
2015
Consider an instance $$I$$I of the random $$k$$k-constraint satisfaction problem ($$k$$k-CSP) with $$n$$n variables and $$t=r\frac{n\ln d}{-\ln (1-p)}$$t=rnlnd-ln(1-p) constraints, where $$d$$d is the domain size of each variable and $$p$$p determines the tightness of the constraints. Suppose that $$d\ge 2$$d?2, $$r>0$$r>0 and $$01/2$$?>1/2. We prove that $$\begin{aligned} \nonumber \lim _{n\rightarrow \infty }\mathbf{ Pr } [I\ \text{ is } \text{ satisfiable }]=\left\{ \begin{array}{cc} 1 &{}\quad \text{ r } 1. \\ \end{array} \right. \end{aligned}$$limn??Pr[Iissatisfiable]=1r 1.Similar results also hold for the $$k$$k-$$hyper$$hyper-$$\mathbf {F}$$F-$$linear$$linear CSP which is obtained by incorporating certain algebraic structures to the domains and constraint relations of $$k$$k-CSP.
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
9
References
5
Citations
NaN
KQI