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

Polylinear continuations of some discrete functions and an algorithm for finding them

Authors

  • Dostonjon N. Barotov
  • Ruziboy N. Barotov

Keywords:

polylinear functions
harmonic functions
systems of Boolean equations
pseudo-Boolean functions
algorithms

Abstract

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.

Downloads

Published

2023-01-21

Issue

Vol. 24 (2023): Issue 1.

Section

Methods and algorithms of computational mathematics and their applications

Author Biographies

Dostonjon N. Barotov

Financial University under the Government of the Russian Federation
Department of Data Analysis and Machine Learning
• Senior Lecturer

Ruziboy N. Barotov

Khujand state university named after academician Bobojon Gafurov
Department of Mathematical Analysis named after Professor A. Mukhsinov
• Doctoral Student

References

  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.

License

Copyright (c) 2023 Д. Н. Баротов, Р. Н. Баротов

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.