Исследуется порядок гладкости fNR(x1, x2,..., xn) - наименьшего вогнутого продолжения на [0,1]n произвольной булевой функции fB(x1, x2,..., xn). Доказано, что если булева функция fB(x1, x2,..., xn) существенно зависит не более чем от одной переменной, то на [0,1]n её наименьшее вогнутое продолжение fNR(x1, x2,..., xn) бесконечно дифференцируемо, в противном случае продолжение fNR(x1, x2,..., xn) на [0,1]n всего лишь непрерывно. Продемонстрировано применение наименьшего вогнутого продолжения к решению систем булевых уравнений.
Скачать электронную версию публикации
Загружен, раз: 9
- Title О порядке гладкости наименьшего вогнутого продолжения булевой функции
- Headline О порядке гладкости наименьшего вогнутого продолжения булевой функции
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 68
- Date:
- DOI 10.17223/20710410/68/1
Ключевые слова
вогнутое продолжение булевой функции, булева функция, вогнутая функция, глобальная оптимизация, локальный экстремумАвторы
Ссылки
Заикин О. С., Семёнов А. А., Посыпкин М. А. Процедуры построения декомпозиционных множеств для распределенного решения 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.
О порядке гладкости наименьшего вогнутого продолжения булевой функции | Прикладная дискретная математика. 2025. № 68. DOI: 10.17223/20710410/68/1
Скачать полнотекстовую версию
Загружен, раз: 68