Generalization of the Subset Sum Problem and Cubic Forms

封面

如何引用文章

全文:

开放存取 开放存取
受限制的访问 ##reader.subscriptionAccessGranted##
受限制的访问 订阅存取

详细

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.

作者简介

A. Seliverstov

Institute for Information Transmission Problems of the Russian Academy of Sciences (Kharkevich Institute)

编辑信件的主要联系方式.
Email: slvstv@iitp.ru
127051, Moscow, Russia

参考

  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

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».