Полилинейные продолжения некоторых дискретных функций и алгоритм их нахождения
DOI:
https://doi.org/10.26089/NumMet.v24r102Ключевые слова:
полилинейные функции, гармонические функции, системы булевых уравнений, псевдобулевы функции, algorithmsАннотация
Исследована проблема существования и единственности полилинейных продолжений некоторых дискретных функций. Доказано, что для любой булевой функции существует соответствующее полилинейное продолжение и оно единственно. Предложен алгоритм нахождения полилинейного продолжения булевой функции и доказана его корректность. На основе предложенного алгоритма найдены явные формы полилинейных продолжений сначала для булевой функции, а затем для произвольной функции, определенной на множестве вершин n-мерного единичного куба, произвольного куба и параллелепипеда, и в каждом конкретном случае доказана единственность соответствующего полилинейного продолжения.
Библиографические ссылки
- 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).
- 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. - 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. - 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. - 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. - 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. - J. Gu, How to Solve Very Large-Scale Satisfiability Problems , Technical Report UUCS-Tr-88-032, (University of Utah, Salt Lake City, 1988).
- 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. - J. Gu, “Global Optimization for Satisfiability (SAT) Problem,” IEEE Trans. Knowl. Data Eng. 6 (3), 361-381 (1994).
doi 10.1109/69.334864. - 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. - 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).
- 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. - 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.
Загрузки
Опубликован
Как цитировать
Выпуск
Раздел
Лицензия
Copyright (c) 2023 Д. Н. Баротов, Р. Н. Баротов
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
