Дата публикации: 2017

Дата публикации в реестре: 2020-03-03T19:06:07Z

Аннотация:

Изучается генерическая сложность десятой проблемы Гильберта для систем диофантовых уравнений в форме Сколема. Приводится генерический полиномиальный алгоритм, определяющий разрешимость таких систем уравнений над множеством натуральных чисел (без нуля). Доказывается, что проблема разрешимости таких систем уравнений над множеством целых чисел является неразрешимой на любом рекурсивном строго генерическом подмножестве входов. Доказательство этой теоремы проходит также для случая, когда решения ищутся во множестве натуральных чисел с нулём.

Тип: статьи в журналах

Источник: Прикладная дискретная математика. 2017. № 37. С. 100-106