ГлавнаяАрхивО двоичных решениях систем уравнений

О двоичных решениях систем уравнений | Прикладная дискретная математика. 2019. № 45. DOI: 10.17223/20710410/45/3

Решение называется двоичным, если каждая переменная равна нулю или единице. Известно, что трудно найти двоичное решение системы алгебраических уравнений, коэффициенты которых являются целыми числами с малыми абсолютными значениями. Целью работы является обоснование эффективного вероятностного сведения системы к одному новому уравнению в случае, когда существует небольшая разница между числом двоичных решений первого уравнения и числом двоичных решений всей системы. Более того, если первое уравнение линейное, то существует алгоритм псевдополиномиального времени для проверки правильности такого сведения к новому уравнению в общем случае.
  • Title О двоичных решениях систем уравнений
  • Headline О двоичных решениях систем уравнений
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 45
  • Date:
  • DOI 10.17223/20710410/45/3
Ключевые слова
алгебраическое уравнение, вероятностный алгоритм, вычислительная сложность, algebraic equation, probabilistic algorithm, computational complexity
Авторы
Ссылки
Seliverstov A. V. Binary solutions to some systems of linear equations // OPTA 2018. Communications in Computer and Information Science. V. 871. Cham: Springer, 2018. P. 183-192. https://doi.org/10.1007/978-3-319-93800-4_15
Схрейвер А. Теория линейного и целочисленного программирования. Т. 2. М.: Мир, 1991. 344 с
Смолев В. В. Об одном подходе к решению булевого линейного уравнения с целыми положительными коэффициентами // Дискретная математика. 1993. Т. 5. № 3. С. 81-89
Gal A., Jang J.-T., Limaye N., et al. Space-efficient approximations for Subset Sum // ACM Trans. Computation Theory. 2016. V. 8. No. 4. Article 16. https://doi.org/10.1145/ 2894843
Bringmann K. A near-linear pseudopolynomial time algorithm for subset sum // SODA'17 Proc. Twenty-Eighth Ann. ACM-SIAM Symp. on Discrete Algorithms. Philadelphia: SIAM, 2017. P. 1073-1084
Koiliaris K. and Xu C. A faster pseudopolynomial time algorithm for subset sum // SODA'17 Proc. Twenty-Eighth Ann. ACM-SIAM Symp. on Discrete Algorithms. Philadelphia: SIAM, 2017. P. 1062-1072
Bateni M. H., Hajiaghayi M. T., Seddighin S., and Stein C. Fast algorithms for knapsack via convolution and prediction // Proc. 50th Ann. ACM SIGACT Symp. on the Theory of Computing (STOC'18). N.Y.: ACM, 2018. P. 1269-1282. https://doi.org/10.1145/ 3188745.3188876
Curtis V. V. and Sanches C. A. A. An improved balanced algorithm for the subsetsum problem // Europ. J. Operat. Res. 2019. V. 275. P. 460-466. https://doi.org/10.1016/ j.ejor.2018.11.055
Cygan M., Mucha M., We˛grzycki K., and W lodarczyk M. On problems equivalent to (min,+)- convolution // ACM Trans. Algorithms. 2019. V. 15. No. 1. Article 14. https://doi.org/10. 1145/3293465
Kapovich I., Miasnikov A., Schupp P., and Shpilrain V. Generic-case complexity, decision problems in group theory and random walks // J. Algebra. 2003. V. 264. No. 2. P. 665-694. https://doi.org/10.1016/S0021-8693(03)00167-4
Рыбалов А. Н. О генерической сложности проблемы разрешимости систем диофантовых уравнений в форме Сколема // Прикладная дискретная математика. 2017. № 37. С. 100-106
Рыбалов А. Н. О генерической NP-полноте проблемы выполнимости булевых формул // Прикладная дискретная математика. 2017. № 36. С. 106-112
Рыбалов А. Н. Релятивизованные генерические классы P и NP // Прикладная дискретная математика. 2018. № 40. С. 100-104
Lyubetsky V. A., Gershgorin R. A., and Gorbunov K. Yu. Chromosome structures: reduction of certain problems with unequal gene content and gene paralogs to integer linear programming // BMC Bioinformatics. 2017. V. 18. No. 40. https://doi.org/10.1186/ s12859-017-1944-x
Schwartz J. T. Fast probabilistic algorithms for verification of polynomial identities // J. ACM. 1980. V. 27. No. 4. P. 701-717. https://doi.org/10.1145/322217.322225
Bacher A., Bodini O., Hwang H.-K., and Tsai T.-H. Generating random permutations by coin-tossing: classical algorithms, new analysis, and modern implementation // ACM Trans. Algorithms. 2017. V. 13. No. 2. Article 24. https://doi.org/10.1145/3009909
О двоичных решениях систем уравнений | Прикладная дискретная математика. 2019. № 45. DOI: 10.17223/20710410/45/3
О двоичных решениях систем уравнений | Прикладная дискретная математика. 2019. № 45. DOI: 10.17223/20710410/45/3