Polylinear continuations of some discrete functions and an algorithm for finding them
Keywords:polylinear functions, harmonic functions, systems of Boolean equations, pseudo-Boolean functions, algorithms
In this paper, we study the existence and uniqueness of polylinear continuations of some discrete functions. It is proved that for any Boolean function, there exists a corresponding polylinear continuation and it is unique. An algorithm for finding a polylinear continuation of a Boolean function is proposed and its correctness is proved. Based on the result of the proposed algorithm, explicit forms of polylinear continuations are found first for a Boolean function and then for an arbitrary function defined only at the vertices of an n-dimensional unit cube, an arbitrary cube, and a parallelepiped, and in each particular case the uniqueness of the corresponding polylinear continuations is proved.
- 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).
- D. N. Barotov and R. N. Barotov, “Polylinear Transformation Method for Solving Systems of Logical Equations,” Mathematics 10 (6), Article Number 918 (2022).
- D. Barotov, A. Osipov, S. Korchagin, et al., “Transformation Method for Solving System of Boolean Algebraic Equations,” Mathematics 9 (24), Article Number 3299 (2021).
- 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).
- 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).
- J. Gu, Q. Gu, and D. Du, “On Optimizing the Satisfiability (SAT) Problem,” J. Comput. Sci. Technol. 14 (1), 1-17 (1999).
- 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).
- 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).
How to Cite
Copyright (c) 2023 Д. Н. Баротов, Р. Н. Баротов
This work is licensed under a Creative Commons Attribution 4.0 International License.