RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



ПДМ:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


ПДМ, 2017, номер 37, страницы 100–106 (Mi pdm595)  

Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)

Математические основы информатики и программирования

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

А. Н. Рыбаловab

a Омский государственный университет им. Ф. М. Достоевского, г. Омск, Россия
b Институт математики им. С.Л. Соболева СО РАН, г. Новосибирск, Россия

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

Ключевые слова: генерическая сложность, диофантовы уравнения.

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 15-41-04312
Работа поддержана грантом РФФИ № 15-41-04312.


DOI: https://doi.org/10.17223/20710410/37/8

Полный текст: PDF файл (629 kB)
Список литературы: PDF файл   HTML файл

Тип публикации: Статья
УДК: 510.52

Образец цитирования: А. Н. Рыбалов, “О генерической сложности проблемы разрешимости систем диофантовых уравнений в форме Сколема”, ПДМ, 2017, № 37, 100–106

Цитирование в формате AMSBIB
\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}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/pdm595
  • http://mi.mathnet.ru/rus/pdm/y2017/i3/p100

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. А. Н. Рыбалов, “О генерической неразрешимости десятой проблемы Гильберта для полиномиальных деревьев”, ПДМ, 2019, № 44, 107–112  mathnet  crossref
    2. А. В. Селиверстов, “О двоичных решениях систем уравнений”, ПДМ, 2019, № 45, 26–32  mathnet  crossref
    3. 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  crossref  isi  scopus
  • Прикладная дискретная математика
    Просмотров:
    Эта страница:72
    Полный текст:18
    Литература:15
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020