Изучается генерическая сложность проблемы проверки совместности систем уравнений над натуральными числами со сложением. Доказывается NP-полнота этой проблемы, предлагается полиномиальный генерический алгоритм её решения. Доказывается, что при Р ≠ NP и Р = ВРР для проблемы проверки совместности систем уравнений над натуральными числами с нулём не существует сильно генерического полиномиального алгоритма. Для сильно генерического полиномиального алгоритма нет эффективного метода случайной генерации входов, на которых этот алгоритм не может решить проблему.
Скачать электронную версию публикации
Загружен, раз: 5
- Title О генерической сложности решения уравнений над натуральными числами со сложением
- Headline О генерической сложности решения уравнений над натуральными числами со сложением
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 64
- Date:
- DOI 10.17223/20710410/64/6
Ключевые слова
генерическая сложность, линейные уравнения, натуральные числаАвторы
Ссылки
Kapovich L, 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.
Gilman R. H., Myasnikov A., and Roman'kov V. Random equations in free groups // Groups Complexity Cryptology. 2011. V.3. No. 2. P.257-284.
Gilman R. H., Myasnikov A., and Roman'kov V. Random equations in nilpotent groups //j. Algebra. 2012. V.352. No. 1. P. 192-214.
Rybalov A. Generic complexity of the Diophantine problem // Groups Complexity Cryptology. 2013. V.5. No. 1. P.25-30.
Rybalov A. and Shevlyakov A. Generic complexity of solving of equations in finite groups, semigroups and fields //j. Physics: Conf. Ser. 2021. V. 1901. Article 012047. 8p.
Shevlyakov A. Algebraic geometry over the additive monoid of natural numbers: The classifcation of coordinate monoids // Groups Complexity Cryptology. 2010. V. 2. No. 1. P.91-111.
Шевляков A. H. Алгебраическая геометрия над моноидом натуральных чисел. Неприводимые алгебраические множества // Труды Института математики и механики УрО РАН. 2010. Т. 16. №2. С. 258-269.
Kryvyi S. L.Compatibility of systems of linear constraints over the set of natural numbers // Cybernetics Systems Analysis. 2002. V. 38. No. 1. P. 17-29.
Китаев А., Шенъ А., Вялый M. Классические и квантовые вычисления. М.: Ml LI INK). ЧеРо, 1999. 192 c.
Схрейвер А. Теория линейного и целочисленного программирования. М.: Мир, 1991. 360 с.
О генерической сложности решения уравнений над натуральными числами со сложением | Прикладная дискретная математика. 2024. № 64. DOI: 10.17223/20710410/64/6
Скачать полнотекстовую версию
Загружен, раз: 139