|
Satisfiability of random systems of equations with nonuniform sampling of two-valued unknowns
A. V. Shapovalov TVP Laboratory, Moscow
Abstract:
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.
Key words:
system of discrete equations, satisfiability, probabilistic algorithms, random hypergraphs.
Received 01.XI.2010
Citation:
A. V. Shapovalov, “Satisfiability of random systems of equations with nonuniform sampling of two-valued unknowns”, Mat. Vopr. Kriptogr., 2:4 (2011), 109–146
Linking options:
https://www.mathnet.ru/eng/mvk46https://doi.org/10.4213/mvk46 https://www.mathnet.ru/eng/mvk/v2/i4/p109
|
Statistics & downloads: |
Abstract page: | 340 | Full-text PDF : | 213 | References: | 51 | First page: | 1 |
|