Solving Large Systems of Boolean Equations

Solving Large Systems of Boolean Equations

Arkadij Zakrevskij (National Academy of Science, Belarus)
DOI: 10.4018/978-1-4666-1900-5.ch002
OnDemand PDF Download:
No Current Special Offers


Systems of many Boolean equations with many variables are regarded, which have a lot of practical applications in logic design and diagnostics, pattern recognition, artificial intelligence, et cetera. Special attention is paid to systems of linear equations playing an important role in information security problems. A compact matrix representation is suggested for such systems. A series of original methods and algorithms for their solution is surveyed in this chapter, as well as the information concerning their program implementation and experimental estimation of their efficiency.
Chapter Preview

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 Te the levels of which correspond to equations. The second method realizes a scanning procedure over arguments corresponding to levels of the search tree Ta. 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 Te and Ta.

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).

Complete Chapter List

Search this Book: