Computational methods in discrete mathematics

Threshold interpolations in solving nonlinear Boolean equation by method of separating planes

V. G. Nikonov^a, A. N. Shurupov<sup>b

a</sup> Russian Academy of Natural Sciences, Moscow
^b Moscow Technological University, Moscow

Abstract: 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
$$ a_{i1}x_1+\dots+a_{in}x_n\le b_i,\qquad i={1,\dots,k}, $$
is called an implicative threshold $k$-interpolation of the Boolean equation $f(x_1,\dots,x_n)=\gamma$ 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(x_1,\dots,x_n)$ is defined. It is a threshold Boolean function $\tau(x_1,\dots,x_n)$ with the probability $\mathsf P(f(x_1,\dots,x_n)=\tau(x_1,\dots,x_n))=1/2+\delta$, $\delta>0$, where $\delta$ 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 interpolations.

UDC: 512.55

DOI: 10.17223/2226308X/10/64