A Probabilistic Approach to the Dichotomy Problem
Tomasz Łuczak, Jaroslav Nešetřil · SIAM Journal on Computing · 2006
Let ${\mathcal R}(n,k)$ denote the random k‐ary relation defined on the set $[n]=\{1,2,\dots,n\}$. We show that the probability that $([n], {\mathcal R}(n,k))$ is projective tends to one, as either n or k tends to infinity. This result implies that for most relational systems $(B,{{\underline{R}}})$ the ${{\textrm{CSP}}}(B,{{\underline{R}}})$ problem is NP‐complete (and thus that the dichotomy conjecture holds with probability 1), and confirms a conjecture of Rosenberg [I. G. Rosenberg, Rocky Mountain J. Math., 3 (1973), pp. 631–639].