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

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

Аннотация:

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

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

Источник: Прикладная дискретная математика. 2019. № 44. С. 107-112