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

doi:10.17223/20710410/44/8

Эндаумент фонд ТГУ!
Впиши своё имя в историю университета
- Сделать пожертвование -

Add to "Quick Collection"

Description	Size	Format
О генерической неразрешимости десятой проблемы Гильберта для полиномиальных деревьев	149 KB	Adobe Acrobat PDF	Read	Download
DOI Доступ к ресурсу на сайте издателя			10.17223/20710410/44/8

#генерическая сложность

#Диофантовы уравнения

#Гильберта проблема десятая

Title: О генерической неразрешимости десятой проблемы Гильберта для полиномиальных деревьев
Title: On generic undecidability of Hilbert's tenth problem for polynomial trees
Creator: Рыбалов, Александр Николаевич
Date: 2019
DOI: 10.17223/20710410/44/8
Description: Генерический подход к алгоритмическим проблемам предложен Каповичем, Мясниковым, Шуппом и Шпильрайном в 2003 г. В рамках этого подхода изучается поведение алгоритмов на множестве «почти всех» входов (это множество называется генерическим) и игнорируется его поведение на остальных входах, на которых алгоритм может работать медленно или вообще не останавливаться. В работе изучается генерическая сложность десятой проблемы Гильберта для диофантовых уравнений, представляемых в виде полиномиальных деревьев. Полиномиальное дерево — это бинарное дерево, листья которого помечены переменными или константой 1, а внутренние вершины содержат операции сложения, вычитания или умножения. Любой полином от многих переменных с целыми коэффициентами можно представить в виде такого полиномиального дерева. Доказывается, что проблема разрешимости диофантовых уравнений, представляемых в виде полиномиальных деревьев, является генерически неразрешимой.

Relationships: Show Relationship Browser for this Object
collection(s): Журналы ТГУ
Identifier: смотреть в электронном каталоге НБ ТГУ
Type: статьи в журналах
Source: Прикладная дискретная математика. 2019. № 44. С. 107-112
Language: rus

Created: 11-07-2019

563 Visitors

418 Hits

151 Downloads

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