Generalization of the Subset Sum Problem and Cubic Forms
- Authors: Seliverstov A.V.1
-
Affiliations:
- Institute for Information Transmission Problems of the Russian Academy of Sciences (Kharkevich Institute)
- Issue: Vol 63, No 1 (2023)
- Pages: 51-60
- Section: ОБЩИЕ ЧИСЛЕННЫЕ МЕТОДЫ
- URL: https://journals.rcsi.science/0044-4669/article/view/134287
- DOI: https://doi.org/10.31857/S0044466923010118
- EDN: https://elibrary.ru/LEEUWB
- ID: 134287
Cite item
Abstract
A new algorithm is proposed for deciding whether a system of linear equations has a binary solution over a field of zero characteristic. The algorithm is efficient under a certain constraint on the system of equations. This is a special case of an integer programming problem. In the extended version of the subset sum problem, the weight can be positive or negative. The problem under consideration is equivalent to the analysis of solution existence for several instances of this problem simultaneously. New sufficient conditions are found under which the computational complexity of almost all instances of this problem is polynomial. In fact, the algorithm checks the existence of a cubic hypersurface that passes through each vertex of the unit cube, but does not intersect a given affine subspace. Several heuristic algorithms for solving this problem have been known previously. However, the new methods expand the solution possibilities. Although only the solution existence problem is considered in detail, binary search allows one to find a solution, if any.
About the authors
A. V. Seliverstov
Institute for Information Transmission Problems of the Russian Academy of Sciences (Kharkevich Institute)
Author for correspondence.
Email: slvstv@iitp.ru
127051, Moscow, Russia
References
- Horowitz E., Sahni S. Computing partitions with applications to the knapsack problem // J. ACM. 1974. V. 21. № 2. P. 277–292. https://doi.org/10.1145/321812.321823
- Meer K. A note on a result for a restricted class of real machines // J. Complexity. 1992. V. 8. № 4. P. 451–453. https://doi.org/10.1016/0885-064X(92)90007-X10.1016/0885-064X(92)90007-X
- Koiran P. Computing over the reals with addition and order // Theoret. Comput. Sci. 1994. V. 133. № 1. P. 35–47. https://doi.org/10.1016/0304-3975(93)00063-B
- Cucker F., Matamala M. On digital nondeterminism // Math. Systems Theory. 1996. V. 29. P. 635–647. https://doi.org/10.1007/BF01301968
- Grigoriev D. Complexity of Positivstellensatz proofs for the knapsack // Comput. Complexity. 2001. V. 10. P. 139–154. https://doi.org/10.1007/s00037-001-8192-0
- Margulies S., Onn S., Pasechnik D.V. On the complexity of Hilbert refutations for partition // J. Symbolic Comput. 2015. V. 66. P. 70–83. https://doi.org/10.1016/j.jsc.2013.06.005
- Koiliaris K., Xu C. Faster pseudopolynomial time algorithms for subset sum // ACM Trans. Algorithms. 2019. V. 15. № 3. Article 40. P. 1–20. https://doi.org/10.1145/3329863
- Polak A., Rohwedder L., Wegrzycki K. Knapsack and subset sum with small items // In: Bansal N., Merelli E., Worrell J. (eds) 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, 2021. V. 198. № 106. P. 1–19. https://doi.org/10.4230/LIPIcs.ICALP.2021.106
- Lagarias J.C., Odlyzko A.M. Solving low-density subset sum problems // J. ACM. 1985. V. 32. № 1. P. 229–246. https://doi.org/10.1145/2455.2461
- Coster M.J., Joux A., LaMacchia B.A., Odlyzko A.M., Schnorr C.P., Stern J. Improved low-density subset sum algorithms // Comput. Complexity. 1992. V. 2. № 2. P. 111–128. https://doi.org/10.1007/BF01201999
- May A. Solving subset sum with small space – Handling cryptanalytic Big Data // it – Information Technology. 2020. V. 62. № 3–4. P. 181–187. https://doi.org/10.1515/itit-2019-0038
- Рыбалов А.Н. О генерической сложности проблемы о сумме подмножеств для полугрупп целочисленных матриц // Прикладная дискретная математика. 2020. № 50. С. 118–126. https://doi.org/10.17223/20710410/50/9
- Кузюрин Н.Н. Полиномиальный в среднем алгоритм в целочисленном линейном программировании // Сиб. журн. исслед. опер. 1994. Т. 1. № 3. С. 38–48.
- Kuzyurin N.N. An integer linear programming algorithm polynomial in the average case // In: Korshunov A.D. (eds.) Discrete Analysis and Operations Research. Mathematics and Its Applications. V. 355. P. 143–152. Springer, Dordrecht, 1996. https://doi.org/10.1007/978-94-009-1606-7
- Селиверстов А.В. Двоичные решения для больших систем линейных уравнений // Прикладная дискретная математика. 2021. № 52. С. 5–15. https://doi.org/10.17223/20710410/52/1
- Pan Y., Zhang F. Solving low-density multiple subset sum problems with SVP oracle // J. Syst. Sci. Complex. 2016. V. 29. P. 228–242. https://doi.org/10.1007/s11424-015-3324-9
- Селиверстов А.В. О двоичных решениях систем уравнений // Прикладная Дискретная Математика. 2019. № 45. С. 26–32. https://doi.org/10.17223/20710410/45/3
- Martins J.P., Ribas B.C. A randomized heuristic repair for the multidimensional knapsack problem // Optim. Lett. 2021. V. 15. P. 337–355. https://doi.org/10.1007/s11590-020-01611-1
- Cacchiani V., Iori M., Locatelli A., Martello S. Knapsack problems – An overview of recent advances. Part II: Multiple, multidimensional, and quadratic knapsack problems // Comput. and Operat. Res. 2022. V. 143. № 105693. P. 1–14. https://doi.org/10.1016/j.cor.2021.105693
- Gribanov D.V., Zolotykh N.Y. On lattice point counting in -modular polyhedra // Optim. Lett. 2022. V. 16. P. 1991–2018. https://doi.org/10.1007/s11590-021-01744-x10.1007/s11590-021-01744-x
- Al-Shihabi S. A novel core-based optimization framework for binary integer programs – the multidemand multidimesional knapsack problem as a test problem // Operat. Res. Perspectiv. 2021. V. 8. № 100182. P. 1–13. https://doi.org/10.1016/j.orp.2021.100182
- Лотов А.В., Рябиков А.И. Дополненный метод стартовой площадки для аппроксимации границы Парето в задачах с многоэкстремальными критериями // Ж. вычисл. матем. и матем. физ. 2021. Т. 61. № 10. С. 1734–1744. https://doi.org/10.31857/S0044466921100100
- Жадан В.Г. Прямо-двойственный метод Ньютона с наискорейшим спуском для линейной задачи полуопределенного программирования. Ньютоновская система уравнений // Ж. вычисл. матем. и матем. физ. 2022. Т. 62. № 2. С. 232–248. https://doi.org/10.31857/S0044466922020132
- Fu H., Xu Y., Wu G., Liu J., Chen S., He X. Emphasis on the flipping variable: Towards effective local search for hard random satisfiability // Informat. Sci. 2021. V. 566. P. 118–139. https://doi.org/10.1016/j.ins.2021.03.009
- Fu H., Liu J., Wu G., Xu Y., Sutcliffe G. Improving probability selection based weights for satisfiability problems // Knowledge-Based Systems. 2022. V. 245. № 108572. P. 1–17. https://doi.org/10.1016/j.knosys.2022.108572
- Guo P., Zhang Y. ISSATA: An algorithm for solving the 3-satisfiability problem based on improved strategy // Applied Intelligence. 2022. V. 52. P. 1740–1751. https://doi.org/10.1007/s10489-021-02493-1
- Cai S., Lei Z. Old techniques in new ways: Clause weighting, unit propagation and hybridization for maximum satisfiability // Artificial Intelligence. 2020. V. 287. № 103354. P. 1–14. https://doi.org/10.1016/j.artint.2020.103354
- Li W., Xu C., Yang Y., Chen J., Wang J. A refined branching algorithm for the maximum satisfiability problem // Algorithmica. 2022. V. 84. P. 982–1006. https://doi.org/10.1007/s00453-022-00938-8
- Абрамов С.А. Лекции о сложности алгоритмов. М: МЦНМО, 2012.
- Алаев П.Е., Селиванов В.Л. Поля алгебраических чисел, вычислимые за полиномиальное время. I // А-лгебра и логика. 2019. Т. 58, № 6. С. 673–705. https://doi.org/10.33048/alglog.2019.58.601
- Батхин А.Б. Параметризация дискриминантного множества многочлена // Программирование. 2016. № 2. С. 8–21.
- Селиверстов А.В. Эвристические алгоритмы распознавания некоторых кубических гиперповерхностей // Программирование. 2021. № 1. С. 65–72. https://doi.org/10.31857/S0132347421010106
- Schwartz J. Fast probabilistic algorithms for verification of polynomial identities // J. ACM. 1980. V. 27. № 4. P. 701–717. https://doi.org/10.1145/322217.322225
- Halbeisen L., Hungerbühler N., Schumacher S. Magic sets for polynomials of degree // Linear Algebra Appl. 2021. V. 609. P. 413–441. https://doi.org/10.1016/j.laa.2020.09.02610.1016/j.laa.2020.09.026
- Chistov A.L. Fast parallel calculation of the rank of matrices over a field of arbitrary characteristic // In: L. Budach (eds) Fundamentals of Computation Theory. FCT 1985. Lecture Notes in Computer Science, vol. 199. Springer, Berlin, Heidelberg, 1985. P. 63–69. https://doi.org/10.1007/BFb0028792
- Mulmuley K. A fast parallel algorithm to compute the rank of a matrix over an arbitrary field // Combinatorica. 1987. V. 7. № 1. P. 101–104. https://doi.org/10.1007/BF02579205
- Переславцева О.Н. О вычислении характеристического полинома матрицы // Дискретная матем. 2011. Т. 23. № 1. С. 28–45. https://doi.org/10.4213/dm1128
- Cheung H.Y., Kwok T.C., Lau L.C. Fast matrix rank algorithms and applications // J. ACM. 2013. V. 60. № 5. Article № 31. P. 1–25. https://doi.org/10.1145/2528404
- Malaschonok G.I., Seliverstov A.V. Calculation of integrals in MathPartner // Discrete and Continuous Model. and Appl. Comput. Sci. 2021. V. 29. № 4. P. 337–346. https://doi.org/10.22363/2658-4670-2021-29-4-337-346
- Seliverstov A.V., Lyubetsky V.A. About forms equal to zero at each vertex of a cube // J. of Communicat. Techn. and Electron. 2012. V. 57. № 8. P. 892–895. https://doi.org/10.1134/S1064226912080049