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

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