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

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

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



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






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


ПДМ, 2019, номер 44, страницы 107–112 (Mi pdm664)  

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

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

А. Н. Рыбалов

Институт математики им. С. Л. Соболева СО РАН, г. Омск, Россия

Аннотация: Генерический подход к алгоритмическим проблемам предложен Каповичем, Мясниковым, Шуппом и Шпильрайном в 2003 г. В рамках этого подхода изучается поведение алгоритмов на множестве «почти всех» входов (это множество называется генерическим) и игнорируется его поведение на остальных входах, на которых алгоритм может работать медленно или вообще не останавливаться. В работе изучается генерическая сложность десятой проблемы Гильберта для диофантовых уравнений, представляемых в виде полиномиальных деревьев. Полиномиальное дерево — это бинарное дерево, листья которого помечены переменными или константой 1, а внутренние вершины содержат операции сложения, вычитания или умножения. Любой полином от многих переменных с целыми коэффициентами можно представить в виде такого полиномиального дерева. Доказывается, что проблема разрешимости диофантовых уравнений, представляемых в виде полиномиальных деревьев, является генерически неразрешимой.

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

Финансовая поддержка Номер гранта
Сибирское отделение Российской академии наук I.1.1.4, проект № 0314-2019-0004
Исследование поддержано программой фундаментальных научных исследований СО РАН I.1.1.4, проект № 0314-2019-0004.


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

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

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

Образец цитирования: А. Н. Рыбалов, “О генерической неразрешимости десятой проблемы Гильберта для полиномиальных деревьев”, ПДМ, 2019, № 44, 107–112

Цитирование в формате AMSBIB
\RBibitem{Ryb19}
\by А.~Н.~Рыбалов
\paper О генерической неразрешимости десятой проблемы Гильберта для полиномиальных деревьев
\jour ПДМ
\yr 2019
\issue 44
\pages 107--112
\mathnet{http://mi.mathnet.ru/pdm664}
\crossref{https://doi.org/10.17223/20710410/44/8}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/pdm664
  • http://mi.mathnet.ru/rus/pdm/y2019/i2/p107

    ОТПРАВИТЬ: 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
  • Прикладная дискретная математика
    Просмотров:
    Эта страница:97
    Полный текст:17
    Литература:3
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020