Geodesic
Threshold interpolations in solving nonlinear Boolean equation by method of separating planes
Prikladnaya Diskretnaya Matematika. Supplement, no. 10 (2017), pp. 165-168.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{PDMA_2017_10_a63,
     author = {V. G. Nikonov and A. N. Shurupov},
     title = {Threshold interpolations in solving nonlinear {Boolean} equation by method of separating planes},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {165--168},
     publisher = {mathdoc},
     number = {10},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2017_10_a63/}
}
TY  - JOUR
AU  - V. G. Nikonov
AU  - A. N. Shurupov
TI  - Threshold interpolations in solving nonlinear Boolean equation by method of separating planes
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2017
SP  - 165
EP  - 168
IS  - 10
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2017_10_a63/
LA  - ru
ID  - PDMA_2017_10_a63
ER  - 
%0 Journal Article
%A V. G. Nikonov
%A A. N. Shurupov
%T Threshold interpolations in solving nonlinear Boolean equation by method of separating planes
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2017
%P 165-168
%N 10
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2017_10_a63/
%G ru
%F PDMA_2017_10_a63
V. G. Nikonov; A. N. Shurupov. Threshold interpolations in solving nonlinear Boolean equation by method of separating planes. Prikladnaya Diskretnaya Matematika. Supplement, no. 10 (2017), pp. 165-168. http://geodesic.mathdoc.fr/item/PDMA_2017_10_a63/

[1] Balakin G. V., Nikonov V. G., “Metody svedeniya bulevykh uravnenii k sistemam porogovykh sootnoshenii”, Obozrenie prikladnoi i promyshlennoi matematiki, 1:3 (1994), 389–401 | Zbl

[2] Rybnikov K. K., “Otsenki slozhnosti nekotorykh skhem metoda razdelyayuschikh ploskostei pri reshenii sistem bulevykh uravnenii”, Obozrenie prikladnoi i promyshlennoi matematiki, 2:9 (2002), 442–443

[3] Anashkina N. V., Shurupov A. N., “Primenenie algoritmov lokalnogo poiska k resheniyu sistem psevdobulevykh lineinykh neravenstv”, Prikladnaya diskretnaya matematika. Prilozhenie, 2015, no. 8, 136–138 | DOI