Solving Large Systems of Boolean Equations

Search Tree Minimization

Two combinatorial methods using tree searching technique could be applied to solve large SLEs: the equation scanning method and the argument scanning method. The first method is implementing consecutive multiplication of orthogonal DNFs of the equations from the considered system and uses the search tree T_e the levels of which correspond to equations. The second method realizes a scanning procedure over arguments corresponding to levels of the search tree T_a. In both cases the run-time is roughly proportional to the size of the tree, i.e. to the number of its nodes. Two original algorithms were worked out that considerably reduce that number in trees T_e and T_a.

Solving large SLE can be considerably accelerated by the described below methods taking into account only the matrix of arguments W (Zakrevskij A. & Zakrevski L., 2002; Zakrevskij & Vasilkova, 2002).