Consistency and an algorithm recognising inconsistency of realisations of a~system of random discrete equations with two-valued unknowns

A. V. Shapovalov

Diskretnaya Matematika, Tome 20 (2008) no. 3, pp. 28-39

Résumé

We consider a random system of discrete equations in $n$ two-valued unknowns consisting of $M=M(n)$ equations. The functions in the left-hand sides of equations are randomly selected from a finite set of functions and can depend on at most $m$ variables. We suggest and justify a criterion of existence of a threshold function for consistency of a random system of equations defined as a function $Q(n)$ for which the probability of consistency of the system tends to one or zero as $n\to\infty$, $M(n)/Q(n)\to0$ or $M(n)/Q(n)\to\infty$ respectively. It is shown that the threshold functions for consistency can be only of the form $n$ and $n^{1-1/r}$, $2\le r\le m+1$, we give criteria of existence of such functions for a random system of equations. For random systems of equations with threshold functions of the form $n^{1-1/r}$, $2\le r\le m+1$, we estimate the probability of consistency as $n\to\infty$ and $M\sim cn^{1-1/r}$ (the probability decreases from one to zero, taking all intermediate values, as $c$ increases from zero to $\infty$) and construct an algorithm recognising inconsistency of realisations of such system of equations. This algorithm has the same limit probability of recognising inconsistency of systems of equations as the algorithm of complete checking of possible solutions but has the lower complexity of order $n^{1-1/r}$ operations.