On the Complexity of the Sequential Sampling Method

A system of Boolean equations can be solved by a sequential sampling method using an -step algorithm, where at the th step the values of all variables essential for the first equations are sampled and false solutions are rejected based on the right-hand sides of the equations, . The estimate of the...

Full description

Saved in:
Bibliographic Details
Published in:Journal of applied and industrial mathematics 2024, Vol.18 (2), p.227-233
Main Author: Fomichev, V. M.
Format: Article
Language:English
Subjects:
Algorithms
Boolean
Complexity
Mathematical analysis
Mathematics
Mathematics and Statistics
Permutations
Sampling methods
Sequential sampling
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A system of Boolean equations can be solved by a sequential sampling method using an -step algorithm, where at the th step the values of all variables essential for the first equations are sampled and false solutions are rejected based on the right-hand sides of the equations, . 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.
ISSN:1990-4789
1990-4797
DOI:10.1134/S1990478924020054