|
On the complexity of the sequential sampling method
V. M. Fomichevab a Security Code LLC, 10 Bld. 1 Pervyi Nagatinskii Driveway, 115230 Moscow, Russia
b Institute of Informatics Problems of FRC CSC RAS, 44 Bld. 2 Vavilov Street, 119333 Moscow, Russia
Abstract:
A system of $m$ Boolean equations can be solved by a sequential sampling method using an $m$-step algorithm, where at the $i$-th step the values of all variables essential for the first $i$ equations are sampled and false solutions are rejected based on the right-hand sides parts of the equations, $i=1,\dots,m$. The estimate of the complexity of the method depends on the structure of the sets of essential variables of the equations and attains its minimum after some permutation of the system equations. For the optimal permutation of equations we propose an algorithm that minimizes the average computational complexity of the algorithm under natural probabilistic assumptions. In a number of cases, the construction of such a permutation is computationally difficult; in this connection, other permutations are proposed which are computed in a simpler way but may lead to nonoptimal estimates of the complexity of the method. The results imply conditions under which the sequential sampling method degenerates into the exhaustive search method. An example of constructing an optimal permutation is given. Tab. 2, illustr. 1, biliogr. 11.
Keywords:
Boolean function, essential variable, subset lattice of a set, chain in a lattice.
Received: 30.03.2023 Revised: 17.10.2023 Accepted: 22.12.2023
Citation:
V. M. Fomichev, “On the complexity of the sequential sampling method”, Diskretn. Anal. Issled. Oper., 31:2 (2024), 144–154; J. Appl. Industr. Math., 18:2 (2024), 227–233
Linking options:
https://www.mathnet.ru/eng/da1350 https://www.mathnet.ru/eng/da/v31/i2/p144
|
Statistics & downloads: |
Abstract page: | 25 | Full-text PDF : | 1 | References: | 9 | First page: | 2 |
|