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.

Bibliographie

[1] Balakin G. V., “Grafy sistem dvuchlennykh uravnenii s bulevymi neizvestnymi”, Teoriya veroyatnostei i ee primeneniya, 40:2 (1995), 241–259 | MR | Zbl

[2] Balakin G. V., “Sistemy sluchainykh uravnenii nad konechnym polem”, Trudy po diskretnoi matematike, 2, 1998, 21–37 | MR | Zbl

[3] Balakin G. V., Kolchin V. F., Khokhlov V. I., “Gipertsikly v sluchainom gipergrafe”, Diskretnaya matematika, 3:3 (1991), 102–108 | MR | Zbl

[4] Zykov A. A., “Gipergrafy”, Uspekhi matem. nauk, 29:6 (1974), 89–154 | MR | Zbl

[5] Kolchin V. F., Sistemy sluchainykh uravnenii, MIEM, Moskva, 1988

[6] Kolchin V. F., “Veroyatnost sovmestnosti odnoi sistemy sluchainykh uravnenii spetsialnogo vida”, Trudy po diskretnoi matematike, 3, 2000, 139–146

[7] Kolchin V. F., Sluchainye grafy, Fizmatlit, Moskva, 2004

[8] Kolchin V. F., Khokhlov V. I., “O chisle tsiklov v sluchainom neravnoveroyatnom grafe”, Diskretnaya matematika, 2:3 (1990), 137–145 | MR | Zbl

[9] Kolchin V. F., Khokhlov V. I., “Porogovyi effekt dlya sistem sluchainykh uravnenii spetsialnogo vida”, Diskretnaya matematika, 7:4 (1995), 29–39 | MR | Zbl

[10] Kopyttsev V. A., “O nekotorykh rezultatakh, svyazannykh s analizom sistem sluchainykh uravnenii”, Vestnik IKSI. Ser. K, Spets. vyp. (2003), 71–75

[11] Sachkov V. N., “Sluchainye neravnoveroyatnye pokrytiya i funktsionalnye uravneniya”, Trudy po diskretnoi matematike, 5, 2002, 205–218

[12] Shapovalov A. V., “Veroyatnost sovmestnosti sluchainykh sistem bulevykh uravnenii”, Diskretnaya matematika, 7:3 (1995), 146–159 | MR | Zbl

[13] Shapovalov A. V., “Porogovye funktsii sovmestnosti sluchainykh sistem uravnenii”, Trudy po diskretnoi matematike, 9, 2006, 377–400

[14] Bollobás B., Random graphs, Academic Press, London, 1985 | MR | Zbl

[15] Erdős P., Rényi A., “On the evolution of random graphs”, Publ. Math. Inst. Hung. Acad. Sci. Ser. A, 5 (1960), 17–61 | MR | Zbl