Generalization of the Subset Sum Problem and Cubic Forms

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

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

  1. 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
  2. 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
  3. 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
  4. Cucker F., Matamala M. On digital nondeterminism // Math. Systems Theory. 1996. V. 29. P. 635–647. https://doi.org/10.1007/BF01301968
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  12. Рыбалов А.Н. О генерической сложности проблемы о сумме подмножеств для полугрупп целочисленных матриц // Прикладная дискретная математика. 2020. № 50. С. 118–126. https://doi.org/10.17223/20710410/50/9
  13. Кузюрин Н.Н. Полиномиальный в среднем алгоритм в целочисленном линейном программировании // Сиб. журн. исслед. опер. 1994. Т. 1. № 3. С. 38–48.
  14. 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
  15. Селиверстов А.В. Двоичные решения для больших систем линейных уравнений // Прикладная дискретная математика. 2021. № 52. С. 5–15. https://doi.org/10.17223/20710410/52/1
  16. 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
  17. Селиверстов А.В. О двоичных решениях систем уравнений // Прикладная Дискретная Математика. 2019. № 45. С. 26–32. https://doi.org/10.17223/20710410/45/3
  18. 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
  19. 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
  20. 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
  21. 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
  22. Лотов А.В., Рябиков А.И. Дополненный метод стартовой площадки для аппроксимации границы Парето в задачах с многоэкстремальными критериями // Ж. вычисл. матем. и матем. физ. 2021. Т. 61. № 10. С. 1734–1744. https://doi.org/10.31857/S0044466921100100
  23. Жадан В.Г. Прямо-двойственный метод Ньютона с наискорейшим спуском для линейной задачи полуопределенного программирования. Ньютоновская система уравнений // Ж. вычисл. матем. и матем. физ. 2022. Т. 62. № 2. С. 232–248. https://doi.org/10.31857/S0044466922020132
  24. 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
  25. 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
  26. 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
  27. 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
  28. 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
  29. Абрамов С.А. Лекции о сложности алгоритмов. М: МЦНМО, 2012.
  30. Алаев П.Е., Селиванов В.Л. Поля алгебраических чисел, вычислимые за полиномиальное время. I // А-лгебра и логика. 2019. Т. 58, № 6. С. 673–705. https://doi.org/10.33048/alglog.2019.58.601
  31. Батхин А.Б. Параметризация дискриминантного множества многочлена // Программирование. 2016. № 2. С. 8–21.
  32. Селиверстов А.В. Эвристические алгоритмы распознавания некоторых кубических гиперповерхностей // Программирование. 2021. № 1. С. 65–72. https://doi.org/10.31857/S0132347421010106
  33. 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
  34. 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
  35. 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
  36. 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
  37. Переславцева О.Н. О вычислении характеристического полинома матрицы // Дискретная матем. 2011. Т. 23. № 1. С. 28–45. https://doi.org/10.4213/dm1128
  38. 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
  39. 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
  40. 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

Copyright (c) 2023 А.В. Селиверстов

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies