Construction of smooth convex extensions of Boolean functions

Cover Page

Cite item

Full Text

Abstract

Systems of Boolean equations are widely used in mathematics, computer science, and applied sciences. In this regard, on the one hand, new research methods and algorithms are being developed for such systems, and on the other hand, existing methods and algorithms for solving such systems are being improved. One of these methods is that, firstly, the system of Boolean equations given over the ring of Boolean polynomials is transformed into a system of equations over the field of real numbers, and secondly, the transformed system is reduced either to the problem of numerical minimization of the corresponding objective function, to a MILP or QUBO problem, to a system of polynomial equations solved on the set of integers, or to an equivalent system of polynomial equations solved by symbolic methods. There are many ways to transform a system of Boolean equations into a continuous minimization problem, since the fundamental difference between such methods and “brute force” local search algorithms is that at each iteration of the algorithm, the shift along the antigradient is performed on all variables simultaneously. But one of the main problems that arise when applying these methods is that the objective function to be minimized in the desired area can have many local minima, which greatly complicates their practical use. In this paper, a non-negative convex and continuously differentiable extension of any Boolean function is constructed, which is applied to solving an arbitrary system of Boolean equations. It is argued that the problem of solving an arbitrary system of Boolean equations can be constructively reduced to the problem of minimizing a function, any local minimum of which in the desired domain is a global minimum.

Full Text

Введение

На протяжении многих десятилетий в истории цифровой науки булевы переменные были основными переменными, используемыми в большинстве компьютерных операций. Встречается много основных задач, связанных с булевыми переменными, а некоторые задачи, несмотря на зрелость области, не имеют удовлетворительных методов решения. Среди них проблема решения булевых и систем булевых уравнений [1]. Эта задача имеет множество приложений, таких как синтез, моделирование и тестирование цифровых сетей и систем СБИС, кодирование выходных данных и назначение состояний конечных автоматов, временной анализ и генерация тестов с задержкой-сбоем для комбинационных схем, автоматическая генерация тестовых шаблонов, определение начального состояния в схемах, содержащих петли обратной связи. В области криптографии булевы уравнения находят применение при анализе и взломе блочных шифров, поскольку их можно свести к проблеме решения крупномасштабной системы булевых уравнений [1–3]. И в настоящем времени теория булевых функций — увлекательная область исследований в области дискретной математики с приложениями к криптографии и теории кодирования [4]. Булевы функции с высокой нелинейностью могут быть использованы для внесения путаницы в алгоритмы блочного шифрования [4, 5]. В связи с этим развивается множество новых направлений исследования и алгоритмов решения систем булевых уравнений. Одно из направлений заключается в том, что, во-первых, система булевых уравнений, заданная над кольцом булевых полиномов, преобразуется в систему уравнений над полем действительных чисел, а во-вторых, преобразованная система сводится либо к задаче численной минимизации соответствующей целевой функции [6–8], либо к задаче MILP или QUBO [9], либо к системе полиномиальных уравнений, решаемой на множестве целых чисел [1], либо к эквивалентной системе полиномиальных уравнений, решаемой символьными методами [10].

Имеется много способов, позволяющих преобразовать систему булевых уравнений в задачу непрерывной минимизации, поскольку принципиальное отличие таких методов от «переборных» алгоритмов локального поиска — на каждой итерации алгоритма сдвиг по антиградиенту производится по всем переменным одновременно [2, 3, 6–8, 11–14]. Но одна из основных проблем, возникающая при применении этих способов, заключается в том, что минимизируемая целевая функция в искомой области может иметь множество локальных минимумов, что значительно усложняет их практическое использование [2, 3, 6–8, 11, 12]. По теореме Д. Н. Баротова, полилинейное продолжение булевой функции играет важную роль в том числе и для уменьшения числа локальных минимумов целевой функции [3, 11]. Недавно в работе [11] были найдены явные формы полилинейных продолжений для произвольных функций, определенных на множестве вершин -мерного единичного куба, произвольного куба и параллелепипеда, и в каждом конкретном случае была доказана единственность соответствующего полилинейного продолжения.

В данной работе конструируется неотрицательное выпуклое и непрерывно дифференцируемое продолжение любой булевой функции и вследствие утверждается, что задача решения произвольной системы булевых уравнений может быть конструктивно сведена к задаче минимизации функции, любой локальный минимум которой в искомой области является глобальным минимумом.

1. Основные понятия

Пусть Bn={(b1,b2,,bn):b1,b2,,bn{0,1}} — множество всевозможных двоичных слов (булевых векторов) длины nKn={(x1,x2,,xn):x1,x2,,xn[0,1]}n-мерный куб, натянутый на булевые векторы длины nint(Kn)={(x1,x2,,xn):x1,x2,,xn(0,1)} — внутренность куба Kn, FK(b1,b2,,bn)n={(x1,x2,,xn)Kn:(2b11)x1+(2b21)x2++(2bn1)xnb1+b2++bn1} — фрагмент куба Kn, противолежащий вершине (b1,b2,,bn)Bn.

Определение 1.1. Функцию f:KnR назовем неотрицательной выпуклой функцией на Kn, если для любых x,yKn и любого α[0,1] выполняется

0f(αx+(1α)y)αf(x)+(1α)f(y).

Определение 1.2. Функцию pC:KnR назовем неотрицательным выпуклым продолжением на Kn булевой функции p:Bn{0,1}, если выполнены два следующих условия:

а) функция pC является выпуклой и неотрицательной на Kn,

b) pC(b1,b2,,bn)=p(b1,b2,,bn)(b1,b2,,bn)Bn.

2. Основные результаты

Лемма 2.1. Для булевой функции Kb1,b2,,bn, заданной формулой

K(b1,b2,,bn)(x1,x2,,xn)=x1b1x2b2xnbn,

существует выпуклое неотрицательное продолжение f(b1,b2,,bn) на Kn. 

Доказательство. Для конструирования искомого продолжения заданной булевой функции сначала покажем, что если f(b1,b2,,bn) — неотрицательное выпуклое продолжение на Kn функции K(b1,b2,,bn), то для любого вектора (x1*,x2*,,xn*)FK(b1,b2,,bn)n выполнено f(b1,b2,,bn)(x1*,x2*,,xn*)=0.

Включение (x1*,x2*,,xn*)FK(b1,b2,,bn)n означает, что

x1,x2,,xna1,a2,,ann\b1,b2,,bnλa1,a2,,ana1,a2,,an

где λ(a1,a2,,an)*0 и (a1,a2,,an)Bn\{(b1,b2,,bn)}λ(a1,a2,,an)*=1. Теперь, с одной стороны, (x1*,x2*,,xn*)Kn и функция f(b1,b2,,bn)(x1,x2,,xn) неотрицательна на Kn и, следовательно, 0f(b1,b2,,bn)(x1*,x2*,,xn*), с другой стороны, в силу неравенства Йенсена [15]

f(b1,b2,,bn)(x1*,x2*,,xn*)=f(b1,b2,,bn)((a1,a2,,an)Bn\{(b1,b2,,bn)}λ(a1,a2,,an)*(a1,a2,,an))

(a1,a2,,an)Bn\{(b1,b2,,bn)}λ(a1,a2,,an)*f(b1,b2,,bn)(a1,a2,,an)

=(a1,a2,,an)Bn\{(b1,b2,,bn)}λ(a1,a2,,an)*0=0.

Из двух полученных неравенств 0f(b1,b2,,bn)(x1*,x2*,,xn*)0 следует, что

f(b1,b2,,bn)(x1*,x2*,,xn*)=0(x1*,x2*,,xn*)FK(b1,b2,,bn)n. (2.1)

Теперь, пусть (x1*,x2*,,xn*)Kn\FK(b1,b2,,bn)n. В этой точке значение функции f(b1,b2,,bn) определим формулой

f(b1,b2,,bn)(x1*,x2*,,xn*)=(1+k=1n((2bk1)xk*bk))2. (2.2)

Заметим, что

f(b1,b2,,bn)(b1,b2,,bn)=(1+k=1n((2bk1)bkbk))2=(1k=1n2bk(1bk))2=1. (2.3)

Таким образом, из равенств (2.1)–(2.3) следует, что сконструированная выше функция f(b1,b2,,bn) неотрицательна и

f(b1,b2,,bn)(a1,a2,,an)=0,если(a1,a2,,an)Bn\{(b1,b2,,bn)},1,если(a1,a2,,an)=(b1,b2,,bn),

=K(b1,b2,,bn)(a1,a2,,an).

Чтобы завершить доказательство, остается показать, что функция f(b1,b2,,bn) является выпуклой на Kn. Объединив (2.1), (2.2), получим

f(b1,b2,,bn)(x1,x2,,xn)=0,если 1+k=1n((2bk1)xkbk)0,(1+k=1n((2bk1)xkbk))2,если 1+k=1n((2bk1)xkbk)0.

Правая часть этого равенства может быть записана в следующем виде

14[(1+k=1n((2bk1)xkbk))+|1+k=1n((2bk1)xkbk)|]2. (2.4)

Используя (2.4), для любых x,yKn и α[0,1] получаем

f(b1,b2,,bn)(αx+(1α)y)=14[k=1n((2bk1)(αxk+(1α)yk)bk)+1

                      +|k=1n(2bk1)(αxk+(1α)yk)bk+1|]2

=14[α(k=1n(2bk1)xkbk+1)+(1α)(k=1n((2bk1)ykbk)+1)

+|α(k=1n(2bk1)xkbk+1)+(1α)(k=1n((2bk1)ykbk)+1)|]2

14[α(k=1n((2bk1)xkbk)+1)+(1α)(k=1n((2bk1)ykbk)+1)

+α|k=1n((2bk1)xkbk)+1|+(1α)|k=1n((2bk1)ykbk)+1|]2

=14[α{k=1n((2bk1)xkbk)+1+|k=1n((2bk1)xkbk)+1|}

+(1α){k=1n((2bk1)ykbk)+1+|k=1n((2bk1)ykbk)+1|}]2

14[α{k=1n((2bk1)xkbk)+1+|k=1n((2bk1)xkbk)+1|}2

+(1α){k=1n((2bk1)ykbk)+1+|k=1n((2bk1)ykbk)+1|}2]

                            =αf(b1,b2,,bn)(x)+(1α)f(b1,b2,,bn)(y).

Таким образом, функция f(b1,b2,,bn) является выпуклой на Kn.  

Замечание 2.1. Неотрицательное выпуклое продолжение на Kn булевой функции K(b1,b2,,bn) является не единственным. Например, если f(b1,b2,,bn) является таким продолжением, то и функция, имеющая значения (f(b1,b2,,bn)(x1,x2,,xn))2, также будет неотрицательным выпуклым продолжением на Kn функции K(b1,b2,,bn). 

Теорема 2.1. Для произвольной булевой функции p:Bn{0,1} существует выпуклое неотрицательное продолжение pC на Kn. 

Доказательство. Пусть задана булева функция p:Bn{0,1}. Используя подходы, предложенные в [11, теорема 2], зададим функцию pC:KnR формулой

pC(x1,x2,,xn)=(b1,b2,,bn)Bnp(b1,b2,,bn)f(b1,b2,,bn)(x1,x2,,xn), (2.5)

где функция f(b1,b2,,bn), являющаяся выпуклым неотрицательным продолжением булевой функции K(b1,b2,,bn), определена в лемме 2.1. Докажем, что функция (2.5) является требуемым продолжением булевой функции p.

Сначала заметим, что в силу определения функция pC выпукла на множестве Kn, так как является суммой выпуклых функций.

Остается проверить, что для любого (a1,a2,,an)Bn выполнено pC(a1,a2,,an)=p(a1,a2,,an). Действительно, в силу леммы 2.1 имеем:

pC(a1,a2,,an)=(b1,b2,,bn)=(a1,a2,,an)p(b1,b2,,bn)f(b1,b2,,bn)(a1,a2,,an)

+(b1,b2,,bn)Bn\(a1,a2,,an)p(b1,b2,,bn)f(b1,b2,,bn)(a1,a2,,an)

=p(a1,a2,,an)f(a1,a2,,an)(a1,a2,,an)

+(b1,b2,,bn)Bn\(a1,a2,,an)p(b1,b2,,bn)0=p(a1,a2,,an).

Итак, доказано, что функция (2.5) является выпуклым неотрицательным продолжением на Kn булевой функции p

Замечание 2.2. Если для булевой функции p выполнено p(x1,x2,,xn)0, то ее неотрицательное выпуклое продолжение pC на Kn определяется единственным образом, причем в этом случае pC(x1,x2,,xn)=0 (x1,x2,,xn)Kn. Действительно, для (x1,x2,,xn)Kn выполнено

0pC(x1,x2,,xn)=pC((1x1)0+x11,x2,,xn)

=pC((1x1)0+x11,(1x1)x2+x1x2,,(1x1)xn+x1xn)

(1x1)pC(0,x2,,xn)+x1pC(1,x2,,xn)

(b1,b2,,bn)BnpC(b1,b2,,bn)k=1n((2bk1)xk+1bk)

=​​​​(b1,b2,,bn)Bn​​p(b1,b2,,bn)k=1n((2bk1)xk+1bk)=​​​​(b1,b2,,bn)Bn​​0k=1n((2bk1)xk+1bk)=0.

Замечание 2.3. Если для булевой функции p выполнено p(x1,x2,,xn)0, то ее неотрицательное выпуклое продолжение pC на Kn не является единственным. Это прямо следует из неединственности функции f(b1,b2,,bn), через которую формулой (2.5) определяется функция pC (см. замечание 2.1).

3. Применение выпуклого продолжения булевой функции к решению системы булевых уравнений

Рассмотрим систему булевых уравнений

p1(x1,x2,,xn)=0,,pm(x1,x2,,xn)=0. (3.1)

Трансформируем эту систему в соответствующую систему выпуклых уравнений

pC1(x1,x2,,xn)=0,,pCm(x1,x2,,xn)=0, (3.2)

где функция pCi — выпуклое продолжение булевой функции pi, i=1,m¯, т. е., как показано при доказательстве теоремы 2.1, может быть определена формулой

pCi(x1,x2,,xn)=(b1,b2,,bn)Bnpi(b1,b2,,bn)f(b1,b2,,bn)(x1,x2,,xn).

Задача решения системы (3.2), очевидно, сводится к задаче минимизации функции p¯C, определяемой соотношением

p¯C(x1,x2,,xn)=i=1npCi(x1,x2,,xn).

Перечислим некоторые свойства функции p¯C, полезные при решении задачи минимизации (в частности, с точки зрения уменьшения количества локальных минимумов).

Свойство 3.1. На множестве Kn функция p¯C выпуклая и непрерывно дифференцируемая.

Свойство 3.2. На множестве Kn любой локальный минимум функции p¯C является также и глобальным минимумом.

Свойство 3.3. Если вектор (s1,s2,,sn)Bn является решением системы (6), то он будет являться решением системы (7) и p¯C(s1,s2,,sn)=0.  

Свойство 3.4. Вектор (r1,r2,,rn)Kn будет решением системы (7) в том и только в том случае, когда p¯C(r1,r2,,rn)=0. 

Справедливость свойств 3.1–3.4 следует из определения функции p¯C.

Авторы выражают искреннюю благодарность рецензенту за полезные замечания и нахождение ряда недостатков, исправление которых помогло улучшить содержание статьи.

×

About the authors

Dostonjon N. Barotov

Financial University under the Government of the Russian Federation

Author for correspondence.
Email: DNBarotov@fa.ru
ORCID iD: 0000-0001-5047-7710

Senior Lecturer, Data Analysis and Machine Learning Department

Russian Federation, 49/2 Leningradsky Prospekt, Moscow 125167

Ruziboy N. Barotov

Khujand State University named after academician Bobojon Gafurov

Email: ruzmet.tj@mail.ru
ORCID iD: 0000-0003-3729-6143

Doctoral Student, Mathematical Analysis named after Professor A. Mukhsinov Department

Russian Federation, 1 Mavlonbekova, Khujand 735700, Republic of Tajikistan

References

  1. A. H. Abdel-Gawad, A. F. Atiya, N. M. Darwish, “Solution of systems of Boolean equations via the integer domain”, Information Sciences, 180:2 (2010), 288–300.
  2. D. N. Barotov, R. N. Barotov, “Polylinear transformation method for solving systems of logical equations”, Mathematics, 10:6 (2022), 918.
  3. D. N. Barotov, “Target function without local minimum for systems of logical equations with a unique solution”, Mathematics, 10:12 (2022), 2097.
  4. J. A. Armario, “Boolean functions and permanents of Sylvester Hadamard matrices”, Mathematics, 9:2 (2021), 177.
  5. L. G. Valiant, “The complexity of computing the permanent”, Theoretical Computer Science, 8:2 (1979), 189–201.
  6. Р. Т. Файзуллин, В. И. Дулькейт, Ю. Ю. Огородников, “Гибридный метод поиска приближенного решения задачи 3 -выполнимость, ассоциированной с задачей факторизации” , Тр. ИММ УрО РАН, 19, 2013, 285–294. [R. T. Faizullin, V. I. Dul’keit, Yu. Yu. Ogorodnikov, “Hybrid method for the approximate solution of the 3-satisfiability problem associated with the factorization problem”, Trudy Inst. Mat. i Mekh. UrO RAN, 19:2 (2013), 285–294 (In Russian)].
  7. J. Gu, “Global optimization for satisfiability (SAT) problem”, IEEE Transactions on Know ledge and DataEngineering, 6:3 (1994), 361–381.
  8. J. Gu, Q. Gu, D. Du, “On optimizing the satisfiability (SAT) problem”, Journal of Computer Science and Technology, 14:1 (1999), 1–17.
  9. A. I. Pakhomchik, V. V. Voloshinov, V. M. Vinokur, G. B. Lesovik, “Converting of Boolean expression to linear equations, inequalities and QUBO penalties for cryptanalysis”, Algorithms, 15:2 (2022), 33.
  10. D. N. Barotov, R. N. Barotov, V. Soloviev, V. Feklin, D. Muzafarov, T. Ergashboev, Kh. Egamov, “The development of suitable inequalities and their application to systems of logical equations”, Mathematics, 10:11 (2022), 1851.
  11. D. N. Barotov, R. N. Barotov, “Polylinear continuations of some discrete functions and an algorithm for finding them”, Numerical Methods and Programming (Vychislitel’nye Metody i Programmirovanie), 24:1 (2023), 10–23.
  12. D. N. Barotov, A. Osipov, S. Korchagin, E. Pleshakova, D. Muzafarov, R. Barotov, D. Serdechnyy, “Transformation method for solving system of Boolean algebraic equations”, Mathematics, 9:24 (2021), 3299.
  13. G. Owen, “Multilinear extensions of games”, Management Science, 18:(5-part-2) (1972), 64–79.
  14. D. M. Wittmann, J. Krumsiek, J. Saez-Rodriguez, D. A. Lauffenburger, S. Klamt, F. J. Theis, “Transforming Boolean models to continuous models: methodology and application to T-cell receptor signaling”, BMC Systems Biology, 3 (2009), 98(2009).
  15. J. L. W. V. Jensen, “Sur les fonctions convexes et les inegalites entre les valeurs moyennes”, Acta Mathematica, 30 (1906), 175–193.

Supplementary files

Supplementary Files
Action
1. JATS XML


Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».