Аннотация:
Изучается генерическая сложность десятой проблемы Гильберта для систем диофантовых уравнений в форме Сколема. Приводится генерический полиномиальный алгоритм, определяющий разрешимость таких систем уравнений над множеством натуральных чисел (без нуля). Доказывается, что проблема разрешимости таких систем уравнений над множеством целых чисел является неразрешимой на любом рекурсивном строго генерическом подмножестве входов. Доказательство этой теоремы проходит также для случая, когда решения ищутся во множестве натуральных чисел с нулём.
Образец цитирования:
А. Н. Рыбалов, “О генерической сложности проблемы разрешимости систем диофантовых уравнений в форме Сколема”, ПДМ, 2017, № 37, 100–106
\RBibitem{Ryb17}
\by А.~Н.~Рыбалов
\paper О генерической сложности проблемы разрешимости систем диофантовых уравнений в~форме Сколема
\jour ПДМ
\yr 2017
\issue 37
\pages 100--106
\mathnet{http://mi.mathnet.ru/pdm595}
\crossref{https://doi.org/10.17223/20710410/37/8}
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/pdm595
https://www.mathnet.ru/rus/pdm/y2017/i3/p100
Эта публикация цитируется в следующих 4 статьяx:
А. В. Селиверстов, “Симметричные матрицы, элементами которых служат линейные функции”, Ж. вычисл. матем. и матем. физ., 60:1 (2020), 109–115; A. V. Seliverstov, “Symmetric matrices whose entries are linear functions”, Comput. Math. Math. Phys., 60:1 (2020), 102–108
А. Н. Рыбалов, “О генерической неразрешимости десятой проблемы Гильберта для полиномиальных деревьев”, ПДМ, 2019, № 44, 107–112
А. В. Селиверстов, “О двоичных решениях систем уравнений”, ПДМ, 2019, № 45, 26–32
A. Rybalov, “On a generic turing reducibility of computably enumerable sets”, Xii International Scientific and Technical Conference Applied Mechanics and Systems Dynamics, Journal of Physics Conference Series, 1210, IOP Publishing Ltd, 2019, 012122
Цитирование в формате AMSBIB
Обратная связь: