ГлавнаяАрхивО генерической сложности проблемы разрешимости систем диофантовых уравнений в форме Сколема

О генерической сложности проблемы разрешимости систем диофантовых уравнений в форме Сколема | Прикладная дискретная математика. 2017. № 37. DOI: 10.17223/20710410/37/8

Изучается генерическая сложность десятой проблемы Гильберта для систем дио-фантовых уравнений в форме Сколема. Приводится генерический полиномиальный алгоритм, определяющий разрешимость таких систем уравнений над множеством натуральных чисел (без нуля). Доказывается, что проблема разрешимости таких систем уравнений над множеством целых чисел является неразрешимой на любом рекурсивном строго генерическом подмножестве входов. Доказательство этой теоремы проходит также для случая, когда решения ищутся во множестве натуральных чисел с нулём.
  • Title О генерической сложности проблемы разрешимости систем диофантовых уравнений в форме Сколема
  • Headline О генерической сложности проблемы разрешимости систем диофантовых уравнений в форме Сколема
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 37
  • Date:
  • DOI 10.17223/20710410/37/8
Ключевые слова
генерическая сложность, диофантовы уравнения, generic complexity, diophantine equations
Авторы
Ссылки
Матиясевич Ю. В. Диофантовость перечислимых множеств // Доклады Академии наук СССР. 1970. Т. 191. №2. С. 279-282.
Matiyasevich Yu. and Robinson J. Reduction of an arbitrary Diophantine equation to one in 13 unknowns // Acta Arithmetica. 1975. V.27. P. 521-553.
Jones J. Undecidable Diophantine equations // Bull. Amer. Math. Soc. 1980. V. 3. No. 2. P. 859-862.
Kapovichl., 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.
Myasnikov A. and Romankov V. Diophantine cryptography in free metabelian groups: Theoretical base // Groups, Complexity, Cryptology. 2014. V.6. No. 2. P. 103-120.
Романьков В. А. Диофантова криптография на бесконечных группах // Прикладная дискретная математика. 2012. №2(16). С. 15-42.
Романьков В. А. Алгебраическая криптография. Омск: ОмГУ, 2013.
Rybalov A. Generic complexity of the Diophantine problem // Groups, Complexity, Cryptology. 2013. V. 5. No. 1. P. 25-30.
Рыбалов А. О генерической неразрешимости Десятой проблемы Гильберта // Вестник Омского университета. 2011. №4. С. 19-22.
Skolem T. Diophantische Gleichungen. Berlin: Springer, 1938.
О генерической сложности проблемы разрешимости систем диофантовых уравнений в форме Сколема | Прикладная дискретная математика. 2017. № 37. DOI: 10.17223/20710410/37/8
О генерической сложности проблемы разрешимости систем диофантовых уравнений в форме Сколема | Прикладная дискретная математика. 2017. № 37. DOI: 10.17223/20710410/37/8