Обобщение задачи о сумме подмножеств и кубические формы

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Только для подписчиков

Аннотация

Предложен новый алгоритм для распознавания существования двоичного решения у системы линейных уравнений над полем нулевой характеристики, который эффективен при выполнении некоторого ограничения на систему уравнений. Это частный случай задачи целочисленного программирования. В расширенной версии задачи о сумме подмножеств вес может быть как положительным, так и отрицательным. Рассмотренная нами задача эквивалентна задаче о существовании решения для нескольких частных случаев этой задачи одновременно. Найдены новые достаточные условия, при которых вычислительная сложность почти всех частных случаев такой задачи полиномиальная. По сути, алгоритм проверяет, существует ли кубическая гиперповерхность, проходящая через каждую вершину единичного куба, но не пересекающая заданное аффинное подпространство. Ранее уже было известно несколько эвристических алгоритмов для решения этой задачи. Однако новые методы расширяют возможности для решения тех или иных задач. Хотя подробно рассмотрена лишь задача распознавания, бинарный поиск позволяет найти решение, если это возможно. Библ. 40.

Об авторах

А. В. Селиверстов

ИППИ РАН

Автор, ответственный за переписку.
Email: slvstv@iitp.ru
Россия, 127051, Москва, Большой Каретный пер., 19, стр. 1

Список литературы

  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

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© А.В. Селиверстов, 2023