Satisfiability of random systems of equations with nonuniform sampling of two-valued unknowns. (Russian. English summary) Zbl 1478.60034
Summary: 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=\text{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.
MSC:
| 60C05 | Combinatorial probability |
| 05C65 | Hypergraphs |
| 05C80 | Random graphs (graph-theoretic aspects) |
References:
| [1] | Balakin G. V., “Grafy sistem dvuchlennykh uravnenii s bulevymi neizvestnymi”, Teoriya veroyatnostei i ee primeneniya, 40:2 (1995), 241-259 · Zbl 0852.60010 |
| [2] | Balakin G. V., “O veroyatnostnom podkhode k resheniyu sistem uravnenii s tselochislennymi neizvestnymi”, Diskret. matem., 7:1 (1995), 88-98 · Zbl 0837.60010 |
| [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 · Zbl 0924.60001 |
| [5] | Balakin G. V., “Sistemy sluchainykh uravnenii nad konechnym polem”, Trudy po diskretnoi matematike, 2, TVP, M., 1998, 21-37 · Zbl 0924.60002 |
| [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 · Zbl 0787.05073 |
| [9] | Zykov A. A., “Gipergrafy”, Uspekhi matem. nauk, 29:6 (1974), 89-154 · Zbl 0307.05134 |
| [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 · Zbl 0997.05001 |
| [13] | Kolchin V. F., Khokhlov V. I., “O chisle tsiklov v sluchainom neravnoveroyatnom grafe”, Diskretn. matem., 2:3 (1990), 137-145 · Zbl 0778.05076 |
| [14] | Kolchin V. F., Khokhlov V. I., “Porogovyi effekt dlya sistem sluchainykh uravnenii spetsialnogo vida”, Diskretn. matem., 7:4 (1995), 29-39 · Zbl 0867.60037 |
| [15] | Kopyttsev V. A., “O raspredelenii chisla reshenii sluchainykh zavedomo sovmestnykh sistem uravnenii”, Teoriya veroyatnostei i ee primeneniya, 40:2 (1995), 430-437 · Zbl 0852.60074 |
| [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 · Zbl 0517.05001 |
| [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 · Zbl 0812.05055 |
| [23] | Shapovalov A. V., “Veroyatnost sovmestnosti sluchainykh sistem bulevykh uravnenii”, Diskretn. matem., 7:2 (1995), 146-159 · Zbl 0835.06015 |
| [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 · Zbl 1181.93080 |
| [26] | Shapovalov A. V., “Kharakteristiki sluchainykh sistem lineinykh uravnenii nad konechnym polem”, Diskretn. matem., 20:4 (2008), 136-146 · Zbl 1182.60006 |
| [27] | Shapovalov A. V., “Predelnye kharakteristiki sluchainykh sistem lineinykh uravnenii nad koltsom vychetov”, Obozrenie prikladnoi i promyshlennoi matematiki, 15:6 (2008), 1003-1018 · Zbl 1199.60246 |
| [28] | Shapovalov A. V., “Kharakteristiki sluchainykh sistem diskretnykh uravnenii pri neravnoveroyatnoi vyborke neizvestnykh”, Matematicheskie voprosy kriptografii, 1:3 (2010), 93-117 · Zbl 1469.60048 |
| [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 · Zbl 0841.90094 |
| [30] | Bollobas B., Random graphs, Academic Press, London etc., 1985 · Zbl 0567.05042 |
| [31] | Creignou N., Daude H., “Smooth and sharp thresholds for random \(k\)-XOR-CNF-formulas satisfiability”, Theoret. Informatics and Appl., 37 (2003), 127-147 · Zbl 1112.68390 · doi:10.1051/ita:2003014 |
| [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 · Zbl 1034.68048 |
| [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 · Zbl 0103.16301 |
| [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 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
