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.

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., “O veroyatnostnom podkhode k resheniyu sistem uravnenii s tselochislennymi neizvestnymi”, Diskret. matem., 7:1 (1995), 88–98 | MR | Zbl

[3] Balakin G. V., “Effektivno reshaemye klassy sistem bulevykh uravnenii”, Obozrenie prikladnoi i promyshlennoi matematiki, 2:3 (1995), 494–501

[4] Balakin G. V., “Vvedenie v teoriyu sluchainykh sistem uravnenii”, Trudy po diskretnoi matematike, 1, TVP, M., 1997, 1–18 | MR | Zbl

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

[6] Balakin G. V., “Sistemy sluchainykh bulevykh uravnenii so sluchainym vyborom neizvestnykh v kazhdom uravnenii”, Trudy po diskretnoi matematike, 3, Fizmatlit, M., 2000, 21–28

[7] Balakin G. V., Bachurin S. A., “Otsenka parametrov metoda posledovatelnogo podbora neizvestnykh”, Trudy po diskretnoi matematike, 6, Fizmatlit, M., 2002, 7–13

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

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

[10] Kolchin V. F., Sistemy sluchainykh uravnenii, MIEM, M., 1988

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

[12] Kolchin V. F., Sluchainye grafy, Fizmatlit, M., 2000 | MR | Zbl

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

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

[15] Kopyttsev V. A., “O raspredelenii chisla reshenii sluchainykh zavedomo sovmestnykh sistem uravnenii”, Teoriya veroyatnostei i ee primeneniya, 40:2 (1995), 430–437 | MR | Zbl

[16] Kopyttsev V. A., “O nekotorykh rezultatakh, svyazannykh s analizom sistem sluchainykh uravnenii”, Vestnik IKSI, Seriya “K”, Spets. vyp., M., 2003, 71–75

[17] Nikonov V. G., Nikonov N. V., “Zaprety $k$-znachnykh funktsii i ikh svyaz s problemoi razreshimosti sistem uravnenii spetsialnogo vida”, Vestnik RUDN. Seriya Prikl. matem. i kompyut. matem., 2:1 (2003), 79–93

[18] Sachkov V. N., Veroyatnostnye metody v kombinatornom analize, Nauka, M., 1978 | MR | Zbl

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

[20] Sachkov V. N., Vvedenie v kombinatornye metody diskretnoi matematiki, Izd. 2-e, MTsNMO, M., 2004

[21] Kharari F., Teoriya grafov, Izd. 3-e, KomKniga, M., 2006

[22] Shapovalov A. V., “O chisle strogo sbalansirovannykh podgrafov sluchainykh odnorodnykh gipergrafov”, Diskretn. matem., 5:4 (1993), 133–144 | MR | Zbl

[23] Shapovalov A. V., “Veroyatnost sovmestnosti sluchainykh sistem bulevykh uravnenii”, Diskretn. matem., 7:2 (1995), 146–159 | MR | Zbl

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

[25] Shapovalov A. V., “Sovmestnost i algoritm raspoznavaniya nesovmestnosti realizatsii sluchainykh sistem diskretnykh uravnenii s dvuznachnymi neizvestnymi”, Diskretn. matem., 20:3 (2008), 28–39 | MR | Zbl

[26] Shapovalov A. V., “Kharakteristiki sluchainykh sistem lineinykh uravnenii nad konechnym polem”, Diskretn. matem., 20:4 (2008), 136–146 | MR | Zbl

[27] Shapovalov A. V., “Predelnye kharakteristiki sluchainykh sistem lineinykh uravnenii nad koltsom vychetov”, Obozrenie prikladnoi i promyshlennoi matematiki, 15:6 (2008), 1003–1018 | Zbl

[28] Shapovalov A. V., “Kharakteristiki sluchainykh sistem diskretnykh uravnenii pri neravnoveroyatnoi vyborke neizvestnykh”, Matematicheskie voprosy kriptografii, 1:3 (2010), 93–117

[29] Balakin G. V., “On the number of solutions of systems of pseudo-boolean random equations”, Veroyatnostn. metody diskretn. matem., Trudy 3-i Petrozavodskoi konferentsii, TVP/VSP, M.–Utrecht, 1993, 71–98 | MR | Zbl

[30] Bollobas B., Random graphs, Academic Press, London etc., 1985 | MR | Zbl

[31] Creignou N., Daude H., “Smooth and sharp thresholds for random $k$-XOR-CNF-formulas satisfiability”, Theoret. Informatics and Appl., 37 (2003), 127–147 | DOI | MR | Zbl

[32] Creignou N., Daude H., Dubois O., “Approximating the satisfiability threshold for random $k$-XOR-formulas”, Comb. Probab. and Comp., 12:2 (2003), 113–126 | MR | Zbl

[33] 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

[34] Shapovalov A. V., “Characteristics of random systems of Boolean equations with non-regular left-hand side”, Probab. Meth. in Discr. Math., Proc. 5-th Int. Petrozavodsk Conf., VSP, Utrecht–Boston–Köln–Tokyo, 2002, 345–350