Satisfiability of random systems of equations with nonuniform sampling of two-valued unknowns

A. V. Shapovalov

Matematičeskie voprosy kriptografii, Tome 2 (2011), pp. 109-146

Résumé

A random system of $M=M(n)$ equations with $n$ two-valued unknowns is considered. Each equation contains at most $m$ unknowns which are selected randomly. We find conditions on the structure of equations ensuring that for $M=cn^{1-1/r}+o(n^{1-1/r})$, $n\to\infty$, $2\le r\le m+1$, $m=\mathrm{const}$, the probability of existence of solution decreases from 1 to 0 when $c$ increases from 0 to $\infty$. An algorithm detecting the unsolvability of a random system of equations is constructed. This algorithm has low time complexity $O(n^{1-1/r})$, $2\le r\le m+1$. The probability of detecting the unsolvability is asymptotically the same as for the exhaustive search algorithm.