О генерической неразрешимости десятой проблемы Гильберта для полиномиальных деревьев | Прикладная дискретная математика. 2019. № 44. DOI: 10.17223/20710410/44/8

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