Properties of random systems of discrete equations with nonuniform sampling of unknowns

A. V. Shapovalov

Matematičeskie voprosy kriptografii, Tome 1 (2010) no. 3, pp. 93-117

Résumé

A random system $S$ of $M=M(n)$ discrete equations with n unkowns is considered. Each equation contains at most m unknowns which are selected at random, independently and (possibly) nonuniformly. We find conditions on the structure of equations ensuring that for $M-c\sqrt n=o(\sqrt n)$, $n\to\infty$, $m=\operatorname{const}$, the limit probability of solvability decreases continuously from $1$ to $0$ when $c$ increases from $0$ to $\infty$. An algorithm detecting the unsolvability of a random system of equations is described. This algorithm has low time complexity $O(\sqrt n)$. The limiting probability of detection the unsolvability is the same as for the exhaustive search algorithm. Our proofs are based on the geometric properties of random system of equations.

Bibliographie

[1] Balakin G. V., “On the number of solutions of systems of pseudo-boolean random equations”, Veroyatnostnye metody diskretnoi matematiki, TVP, M.; VSP, Utrecht, 1993, 71–98 | MR | Zbl

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

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

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

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

[6] Kovalenko I. N., Levitskaya A. A., Savchuk M. N., Izbrannye zadachi veroyatnostnoi kombinatoriki, Naukova dumka, Kiev, 1986, 224 pp. | MR | Zbl

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

[8] Kolchin V. F., Sluchainye grafy, FIZMATLIT, M., 2000 | MR | Zbl

[9] Kolchin V. F., Sevastyanov B. A., Chistyakov V. P., Sluchainye razmescheniya, Nauka, M., 1976, 224 pp. | MR | Zbl

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

[11] Sachkov V. N., “Sluchainye pokrytiya i sistemy funktsionalnykh uravnenii”, Intellektualnye sistemy, 2:1–4 (1997), 297–315

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

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

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

[15] Shapovalov A. V., “Tsiklovaya struktura sluchainogo neodnorodnogo gipergrafa na dokriticheskom etape evolyutsii”, Diskretn. matem., 19:4 (2007), 52–69 | MR

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

[17] Shapovalov A. V., “Sovmestnost i algoritm raspoznavaniya nesovmestnosti realizatsii sluchainoi sistemy diskretnykh uravnenii s neravnoveroyatnoi vyborkoi neizvestnykh”, Obozrenie prikladnoi i promyshlennoi matematiki, 16:2 (2009), 280–281

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