In this paper, we study the order of smoothness of fNR(x1, x2,..., xn) - the least concave extension on [0,1]n of an arbitrary Boolean function fB(x1, x2,..., xn). We prove that if the Boolean function fB(x1, x2,..., xn) essentially depends on at most one variable, then on [0,1]n its least concave extension fNR(x1, x2,..., xn) is infinitely differentiable, otherwise the extension fNR(x1, x2,..., xn) on [0,1]n is only continuous. We demonstrate how the least concave extension can be used to solve systems of Boolean equations.
Download file
Counter downloads: 10
- Title On the order of smoothness of the smallest concave extension of a Boolean function
- Headline On the order of smoothness of the smallest concave extension of a Boolean function
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 68
- Date:
- DOI 10.17223/20710410/68/1
Keywords
concave extension of a Boolean function, Boolean function, concave function, global optimization, local extremumAuthors
References
Заикин О. С., Семёнов А. А., Посыпкин М. А. Процедуры построения декомпозиционных множеств для распределенного решения SAT-задач в проекте добровольных вычислений SAT@home // Управление большими системами. 2013. Вып. 43. С. 138-156.
Заикин О. С., Семенов А. А. Применение метода Монте-Карло к прогнозированию времени параллельного решения проблемы булевой выполнимости // Выч. мет. программирование. 2014. Т. 15. № 1. С. 22-35.
Мальцева М. А., Румянцев А. С. Проверка выполнимости булевых формул с помощью квантового отжига /7 Труды Карельского научного центра РАН. 2023. №4. С. 41-49.
Леонтьев В. К., Нурлыбаев А. Н. Об одном классе систем булевых уравнений // Ж. вычиел. матем. и матом. физ. 1975. Т. 15. №6. С. 1568-1579.
Леонтьев В. К., Тоиоян Г. П. О системах булевых уравнений /7 Ж. вычиел. матсм. и матсм. физ. 2013. Т. 53. № 5. С. 800-807.
Ramos-Calderer S., Bravo-Prieto C., Lin R., et al. Solving systems of Boolean multivariate equations with quantum annealing // Phvs. Rev. Res. 2022. V. 4. No. 1. Paper 013096.
Bennakhi A., Byrd G. T., and Franzon P. Solving the B-SAT problem using quantum computing: Smaller is sometimes better // Entropy. 2024. V. 26. No. 10. Paper 875.
Леонтьев В. К., Тоноян Г. П. Приближенные решения систем булевых уравнений // Ж. ввiчисл. матем. и матем. физ. 1993. Т. 33. №9. С. 1383-1390.
Леонтьев В. К., Гордеев Э. Н. О числе решений системы булевых уравнений // Автомат, и телемех. 2021. №9. С. 150-168.
Gu J. How to Solve Very Large-Scale Satisfiability (VLSS) Problems. Technical Report UCECETR-90-002. Calgary: University of Calgary, 1990.
Gu J. On optimizing a search problem // N. G. Burbakis (ed). Artificial Intelligence Methods and Applications. 1992. P.63-105.
Gu J. Global optimization for satisfiability (SAT) problem // IEEE Trans. Knowledge Data Engin. 1994. V.6. No. 3. P.361-381.
Gu J., Gu Q., and Du D. On optimizing the satisfiability (SAT) problem // J.Computer Sci. Technology. 1999. V. 14. No. 1. P. 1-17.
Barotov D. N. Target function without local minimum for systems of logical equations with a unique solution // Mathematics. 2022. V. 10. No. 12:2097.
Pakhomchik A. I., Voloshinov V. V., Vinokur V.M., and Lesovik G.B. Converting of Boolean expression to linear equations, inequalities and QUBO penalties for cryptanalysis // Algorithms. 2022. V. 15. No. 2:33.
Burek E., Wronski M., Mank K., and Misztal M. Algebraic attacks on block ciphers using quantum annealing // IEEE Trans. Emerging Topics in Computing. 2022. V. 10. No. 2. P.678-689.
Abdel-Gawad A. H., Atiya A. F., and Darwish N. M. Solution of systems of Boolean equations via the integer domain // Inform. Sci. 2010. V. 180. No. 2. P.288-300.
Barotov D. N., Barotov R.N., Soloviev V., et al. The development of suitable inequalities and their application to systems of logical equations // Mathematics. 2022. V. 10. No. 11:1851.
Файзуллин P. T., Дулькейт В. И., Огородников Ю. Ю. Гибридный метод поиска приближенного решения задачи 3-выполнимоств, ассоциированной с задачей факторизации // Труды Института математики и механики УрО РАН. 2013. Т. 19. №2. С. 285-294.
Баротов Д.Н., Баротов Р.Н. Полилинейные продолжения некоторых дискретных функций и алгоритм их нахождения // Выч. мет. программирование. 2023. Т. 24. №1. С.10-23.
Баротов Д.Н., Баротов Р.Н. Конструирование гладких выпуклых продолжений булевых функций // Вестник российских университетов. Математика. 2024. Т. 29. №145. С.20-28.
Баротов Д.Н. Выпуклое продолжение булевой функции и его приложения // Дискрет, анализ исслед. опер. 2024. Т. 31. №1. С. 5-18.
Баротов Д.Н. О существовании и свойствах выпуклых продолжений булевых функций // Матем. заметки. 2024. Т. 115. №4. С.533-551.
Баротов Д.Н. Вогнутые продолжения булевых функций и некоторые их свойства и приложения // Изв. Иркут, ун-та. Сер. Математика. 2024. Т. 49. С. 105-123.
Баротов Д.Н. Выпуклые продолжения некоторых дискретных функций // Дискрет, анализ исслед. опер. 2024. Т.31. №3. С.5-23.
Баротов Д. Н., Судаков В. А. О неравенствах между выпуклыми, вогнутыми и полилинейными продолжениями булевых функций // Препринты НИМ им. М.В. Келдыша. 2024. №30. С. 1-13.
Экланд И., Темам Р. Выпуклый анализ и вариационные проблемы. М.: Мир, 1979. 399 с.
Salomaa A. On essential variables of functions, especially in the algebra of logic // Ann. Acad. Sci. Fenn. Ser. AI Math. 1963. No. 339. P. 1-11.
Jensen J. L. W. V. Sur les fonctions convexes et les inegalites entre les valeurs movennes // Acta Mathematica. 1906. V. 30. No. 1. P. 175-193.
On the order of smoothness of the smallest concave extension of a Boolean function | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2025. № 68. DOI: 10.17223/20710410/68/1
Download full-text version
Counter downloads: 70