OPTIMAL METHOD FOR SOLVING SPECIAL CLASSES OF SYSTEMS OF NONLINEAR EQUATIONS OF THE SECOND DEGREE
DOI:
https://doi.org/10.26577/JMMCS.2023.v118.i2.02Keywords:
Zhegalkin polynomial, linear Boolean functions, homogeneous-identity matrices, polynomial length, disjunctive normal formsAbstract
In order to simplify the notation and reduce the time for solving systems of Boolean equations, a method is proposed that is optimal for solving a separate class of systems of nonlinear Boolean equations of the second degree. In the class of systems of non-linear Boolean equations under study, logical formulas are divided completely or partially into some linear factors. As a result, logical formulas are reduced to a product of linear polynomials, on the basis of which a system of linear Boolean equations is obtained, which is solved an order of magnitude easier than a system of second-order Boolean equations. It is considered some problems of minimization of special disjunctive normal forms obtained from the Zhegalkin polynomial of the second degree of a special class.
References
[1] A. Kabulov, I. Yarashov and A. Otakhonov, "Algorithmic Analysis of the System Based on the Functioning Table and Information Security,"2022 IEEE International IOT, Electronics and Mechatronics Conference (IEMTRONICS), Toronto, ON, Canada, 2022, pp. 1-5, doi: 10.1109/IEMTRONICS55184.2022.9795746
[2] A. Kabulov, I. Saymanov, I. Yarashov and A. Karimov, "Using Algorithmic Modeling to Control User Access Based on Functioning Table,"2022 IEEE International IOT, Electronics and Mechatronics Conference (IEMTRONICS), Toronto, ON, Canada, 2022, pp. 1-5, doi: 10.1109/IEMTRONICS55184.2022.9795850
[3] E. Navruzov and A. Kabulov, "Detection and analysis types of DDoS attack,"2022 IEEE International IOT, Electronics and Mechatronics Conference (IEMTRONICS), Toronto, ON, Canada, 2022, pp. 1-7, doi: 10.1109/IEMTRONICS55184.2022.9795729.
[4] A. Kabulov, I. Saymanov, I. Yarashov and F. Muxammadiev, "Algorithmic method of security of the Internet of Things based on steganographic coding,"2021 IEEE International IOT, Electronics and Mechatronics Conference (IEMTRONICS), Toronto, ON, Canada, 2021, pp. 1-5, doi: 10.1109/IEMTRONICS52119.2021.9422588.
[5] A. Kabulov, I. Normatov, E. Urunbaev and F. Muhammadiev, "Invariant Continuation of Discrete Multi-Valued Functions and Their Implementation,"2021 IEEE International IOT, Electronics and Mechatronics Conference (IEMTRONICS), Toronto, ON, Canada, 2021, pp. 1-6, doi: 10.1109/IEMTRONICS52119.2021.9422486.
[6] A.Kabulov, I. Normatov, A.Seytov and A.Kudaybergenov, "Optimal Management of Water Resources in Large Main Canals with Cascade Pumping Stations,"2020 IEEE International IOT, Electronics and Mechatronics Conference (IEMTRONICS), Vancouver, BC, Canada, 2020, pp. 1-4, doi: 10.1109/IEMTRONICS51293.2020.9216402.
[7] Kabulov, A.V., Normatov, I.H. (2019). About problems of decoding and searching for the maximum upper zero of discrete monotone functions. Journal of Physics: Conference Series, 1260(10), 102006. doi:10.1088/1742-6596/1260/10/102006
[8] Kabulov, A.V., Normatov, I.H. Ashurov A.O. (2019). Computational methods of minimization of multiple functions. Journal of Physics: Conference Series, 1260(10), 10200. doi:10.1088/1742-6596/1260/10/102007
[9] Yablonskii S.V. Vvedenie v diskretnuyumatematiku: Ucheb. posobiedlyavuzov. -2e izd., pererab. idop. -M.:Nauka. Glavnayaredaksiyafiziko-matematicheskoy literature, -384 s.
[10] Djukova, E.V., Zhuravlev, Y.I. Monotone Dualization Problem and Its Generalizations: Asymptotic Estimates of the Number of Solutions. Comput. Math. and Math. Phys. 58, 2064–2077 (2018). https://doi.org/10.1134/S0965542518120102
[11] Leont’ev, V.K. Symmetric boolean polynomials. Comput. Math. and Math. Phys. 50, 1447–1458 (2010). https://doi.org/10.1134/S0965542510080142
[12] Nisan, N. and Szegedy, M. (1991). On the Degree of Boolean Functions as Real Polynomials, in preparation.
[13] RamamohanPaturi. 1992. On the degree of polynomials that approximate symmetric Boolean functions (preliminary version). In Proceedings of the twenty-fourth annual ACM symposium on Theory of Computing (STOC ’92). Association for Computing Machinery, New York, NY, USA, 468–474. https://doi.org/10.1145/129712.129758.
[14] Gu J., Purdom P., Franco J., Wah B.W. Algorithms for the satisfiability (SAT) problem:A Survey // DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 1997.Vol. 35. P. 19–152.
[15] Goldberg E., Novikov Y. BerkMin: A Fast and Robust SAT Solver // Automation andTest in Europe (DATE). 2002. P. 142–149.
[2] A. Kabulov, I. Saymanov, I. Yarashov and A. Karimov, "Using Algorithmic Modeling to Control User Access Based on Functioning Table,"2022 IEEE International IOT, Electronics and Mechatronics Conference (IEMTRONICS), Toronto, ON, Canada, 2022, pp. 1-5, doi: 10.1109/IEMTRONICS55184.2022.9795850
[3] E. Navruzov and A. Kabulov, "Detection and analysis types of DDoS attack,"2022 IEEE International IOT, Electronics and Mechatronics Conference (IEMTRONICS), Toronto, ON, Canada, 2022, pp. 1-7, doi: 10.1109/IEMTRONICS55184.2022.9795729.
[4] A. Kabulov, I. Saymanov, I. Yarashov and F. Muxammadiev, "Algorithmic method of security of the Internet of Things based on steganographic coding,"2021 IEEE International IOT, Electronics and Mechatronics Conference (IEMTRONICS), Toronto, ON, Canada, 2021, pp. 1-5, doi: 10.1109/IEMTRONICS52119.2021.9422588.
[5] A. Kabulov, I. Normatov, E. Urunbaev and F. Muhammadiev, "Invariant Continuation of Discrete Multi-Valued Functions and Their Implementation,"2021 IEEE International IOT, Electronics and Mechatronics Conference (IEMTRONICS), Toronto, ON, Canada, 2021, pp. 1-6, doi: 10.1109/IEMTRONICS52119.2021.9422486.
[6] A.Kabulov, I. Normatov, A.Seytov and A.Kudaybergenov, "Optimal Management of Water Resources in Large Main Canals with Cascade Pumping Stations,"2020 IEEE International IOT, Electronics and Mechatronics Conference (IEMTRONICS), Vancouver, BC, Canada, 2020, pp. 1-4, doi: 10.1109/IEMTRONICS51293.2020.9216402.
[7] Kabulov, A.V., Normatov, I.H. (2019). About problems of decoding and searching for the maximum upper zero of discrete monotone functions. Journal of Physics: Conference Series, 1260(10), 102006. doi:10.1088/1742-6596/1260/10/102006
[8] Kabulov, A.V., Normatov, I.H. Ashurov A.O. (2019). Computational methods of minimization of multiple functions. Journal of Physics: Conference Series, 1260(10), 10200. doi:10.1088/1742-6596/1260/10/102007
[9] Yablonskii S.V. Vvedenie v diskretnuyumatematiku: Ucheb. posobiedlyavuzov. -2e izd., pererab. idop. -M.:Nauka. Glavnayaredaksiyafiziko-matematicheskoy literature, -384 s.
[10] Djukova, E.V., Zhuravlev, Y.I. Monotone Dualization Problem and Its Generalizations: Asymptotic Estimates of the Number of Solutions. Comput. Math. and Math. Phys. 58, 2064–2077 (2018). https://doi.org/10.1134/S0965542518120102
[11] Leont’ev, V.K. Symmetric boolean polynomials. Comput. Math. and Math. Phys. 50, 1447–1458 (2010). https://doi.org/10.1134/S0965542510080142
[12] Nisan, N. and Szegedy, M. (1991). On the Degree of Boolean Functions as Real Polynomials, in preparation.
[13] RamamohanPaturi. 1992. On the degree of polynomials that approximate symmetric Boolean functions (preliminary version). In Proceedings of the twenty-fourth annual ACM symposium on Theory of Computing (STOC ’92). Association for Computing Machinery, New York, NY, USA, 468–474. https://doi.org/10.1145/129712.129758.
[14] Gu J., Purdom P., Franco J., Wah B.W. Algorithms for the satisfiability (SAT) problem:A Survey // DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 1997.Vol. 35. P. 19–152.
[15] Goldberg E., Novikov Y. BerkMin: A Fast and Robust SAT Solver // Automation andTest in Europe (DATE). 2002. P. 142–149.
Downloads
Published
2023-06-30
Issue
Section
Mathematics
