Threshold interpolations in solving nonlinear boolean equation by method of separating planes
For solving non-linear Boolean equation, we consider implicative system of linear inequalities that can have the least number of inequalities and be solved more efficiently than equivalent system of linear inequalities. The implicative system of linear inequalities includes all the solutions of the original Boolean equation and can have another solutions, the number of which - so called deficit - also characterizes the quality of the implicative system. More exactly, for a fixed k, the system of linear inequalities aax1 + ... + ai„x„ ^ bi, i = 1,..., k, is called an implicative threshold k-interpolation of the Boolean equation f (x1,... ,xn) = 7 if all the solutions of this equation are the solutions of the system. As an alternative to this, a statistical threshold interpolation of Boolean function f (x1,... ,xn) is defined. It is a threshold Boolean function т(x1,...,xn) with the probability P(f(x1,...,xn) = = т(x1,... ,xn)) = 1/2 + 5, 5 > 0, where 5 is the quality of the interpolation. Using this notion instead of implicative interpolation can decrease the complexity of solving Boolean equations.
Keywords
метод разделяющих плоскостей, нелинейные булевы уравнения, пороговые функции, пороговые приближения, method of separating planes, non-linear Boolean equations, threshold functions, threshold interpolationsAuthors
| Name | Organization | |
| Nikonov V. G. | Russian Academy of Natural Sciences | |
| Shurupov A.N. | Moscow State University of Information Technologies, Radio Engineering and Electronics | ashurupov@mail.ru |
References
