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 theright-hand sides of the equations, \(i=1,\dots ,m\) . The estimate of the complexity of the method depends on the structure ofthe sets of essential variables of the equations and attains its minimum after some permutation ofthe system equations. For the optimal permutation of equations we propose an algorithm thatminimizes the average computational complexity of the algorithm under natural probabilisticassumptions. In a number of cases, the construction of such a permutation is computationallydifficult; in this connection, other permutations are proposed which are computed in a simpler waybut may lead to nonoptimal estimates of the complexity of the method. The results implyconditions under which the sequential sampling method degenerates into the exhaustive searchmethod. An example of constructing an optimal permutation is given.
