Полилинейные продолжения некоторых дискретных функций и алгоритм их нахождения

Авторы

DOI:

https://doi.org/10.26089/NumMet.v24r102

Ключевые слова:

полилинейные функции, гармонические функции, системы булевых уравнений, псевдобулевы функции, algorithms

Аннотация

Исследована проблема существования и единственности полилинейных продолжений некоторых дискретных функций. Доказано, что для любой булевой функции существует соответствующее полилинейное продолжение и оно единственно. Предложен алгоритм нахождения полилинейного продолжения булевой функции и доказана его корректность. На основе предложенного алгоритма найдены явные формы полилинейных продолжений сначала для булевой функции, а затем для произвольной функции, определенной на множестве вершин n-мерного единичного куба, произвольного куба и параллелепипеда, и в каждом конкретном случае доказана единственность соответствующего полилинейного продолжения.

Авторы

Д. Н. Баротов

Финансовый университет при Правительстве РФ
департамент анализа данных и машинного обучения
4-й Вешняковский проезд, д. 4, 109456, Москва
• старший преподаватель

Р. Н. Баротов

Худжандский государственный университет имени академика Б. Гафурова
кафедра математического анализа имени профессора А. Мухсинова
пр. Мавлонбекова , д. 1, 735700, Худжанд, Таджикистан
• докторант

Библиографические ссылки

  1. R. T. Faizullin, V. I. Dul’keit, and Yu. Yu. Ogorodnikov, “Hybrid Method for the Approximate Solution of the 3-Satisfiability Problem Associated with the Factorization Problem,” Trudy Inst. Mat. Mekh. UrO RAN. 19 (2), 285-294 (2013).
  2. A. H. Abdel-Gawad, A. F. Atiya, and N. M. Darwish, “Solution of Systems of Boolean Equations via the Integer Domain,” Inf. Sci. 180 (2), 288-300 (2010).
    doi 10.1016/j.ins.2009.09.010.
  3. D. N. Barotov and R. N. Barotov, “Polylinear Transformation Method for Solving Systems of Logical Equations,” Mathematics 10 (6), Article Number 918 (2022).
    doi 10.3390/math10060918.
  4. D. Barotov, A. Osipov, S. Korchagin, et al., “Transformation Method for Solving System of Boolean Algebraic Equations,” Mathematics 9 (24), Article Number 3299 (2021).
    doi 10.3390/math9243299.
  5. D. N. Barotov, R. N. Barotov, V. Soloviev, et al., “The Development of Suitable Inequalities and Their Application to Systems of Logical Equations,” Mathematics 10 (11), Article Number 1851 (2022).
    doi 10.3390/math10111851.
  6. R. T. Faizullin, I. G. Khnykin, and V. I. Dylkeyt, The SAT Solving Method as Applied to Cryptographic Analysis of Asymmetric Ciphers , arXiv preprint: 0907.1755v1[cs.CR] (Cornell Univ. Library, Ithaca, 2009),
    https://arxiv.org/abs/0907.1755 . Cited December 18, 2022.
  7. J. Gu, How to Solve Very Large-Scale Satisfiability Problems , Technical Report UUCS-Tr-88-032, (University of Utah, Salt Lake City, 1988).
  8. J. Gu, “On Optimizing a Search Problem,” in Artificial Intelligence: Methods and Applications (World Scientific, Singapore, 1992), pp. 63-105.
    https://books.google.ru/books?id=0a_j0R0qh1EC&printsec=frontcover&hl=ru#v=onepage&q&f=false . Cited December 19, 2022.
  9. J. Gu, “Global Optimization for Satisfiability (SAT) Problem,” IEEE Trans. Knowl. Data Eng. 6 (3), 361-381 (1994).
    doi 10.1109/69.334864.
  10. J. Gu, Q. Gu, and D. Du, “On Optimizing the Satisfiability (SAT) Problem,” J. Comput. Sci. Technol. 14 (1), 1-17 (1999).
    doi 10.1007/BF02952482.
  11. D. N. Barotov, D. Z. Muzafarov, and R. N. Barotov, “On One Method for Solving Systems of Boolean Algebraic Equations,” Mod. Math. Concept Innov. Math. Educ. 8, 17-23 (2021).
  12. D. N. Barotov, “Target Function without Local Minimum for Systems of Logical Equations with a Unique Solution,” Mathematics 10 (12), Article Number 2097 (2022).
    doi 10.3390/math10122097.
  13. E. Ishchukova, E. Maro, and P. Pristalov, “Algebraic Analysis of a Simplified Encryption Algorithm GOST R 34.12-2015,” Computation 8 (2), Article Number 51 (2020).
    doi 10.3390/computation8020051.

Загрузки

Опубликован

21-01-2023

Как цитировать

Баротов Д. Н., Баротов Р. Н. Полилинейные продолжения некоторых дискретных функций и алгоритм их нахождения // Вычислительные методы и программирование. 2023. 24. 10-23. doi 10.26089/NumMet.v24r102

Выпуск

Раздел

Методы и алгоритмы вычислительной математики и их приложения