О сложности целочисленных полиномиальных возвратных последовательностей

Актуальность и цели. Линейные возвратные последовательности представляют собой «классический» объект комбинаторного анализа. Для выражения произвольного члена линейной возвратной последовательности имеются точные формулы экспоненциального типа как в случае поля комплексных чисел, так и в случае конечного поля Галуа. Следующим шагом в изучении возвратных последовательностей явилось бы рассмотрение полиномиальных возвратных последовательностей. Однако даже для возвратных последовательностей над множеством натуральных чисел эта задача пока не решена. Существует предположение, что при переходе к множеству целых чисел для полиномиальных возвратных последовательностей могут появиться алгоритмически неразрешимые проблемы. Тогда, разумеется, никаких формул для вычисления членов полиномиальной возвратной последовательности в общем случае ожидать не следует. Пока это предположение не доказано, целочисленные полиномиальные возвратные последовательности являются практически неисследованным объектом. В начале 2000-х гг. автор предложил рассматривать «почти полиномиальные» возвратные последовательности - последовательности, порождающие функции которых определяются суперпозициями полиномиальных функций и некоторых простых «почти полиномиальных» функций. Как оказалось, при добавлении к множеству полиномиальных функций функции типа $sg(x)$ появляются возвратные последовательности с алгоритмически неразрешимыми проблемами. Это наводит на мысль, что в случае полиномиальных возвратных последовательностей над множеством целых чисел сами возвратные последовательности с алгоритмической точки зрения должны быть устроены достаточно сложно. Обоснование этого предположения и является целью настоящей статьи. Чтобы говорить о сложности возвратных последовательностей, необходимо прежде всего определить инструмент, с помощью которого можно будет оценивать сложность рассматриваемых последовательностей. В качестве такого инструмента выбрана одноленточная машина Тьюринга, работающая в трехбуквенном алфавите. Вычисления на данных машинах Тьюринга удается промоделировать целочисленными возвратными последовательностями с полиномиальной порождающей функцией. В результате для ряда проблем, связанных с возвратными последовательностями этого типа, получаются нижние сверхэкспоненциальные оценки сложности их решения. Материалы и методы. В построениях и доказательствах используются приемы и методы из теории вычислимых функций. Результаты и выводы. Рассматриваются возвратные последовательности над множеством целых чисел с полиномиальными порождающими функциями. С помощью данных последовательностей моделируются вычисления на детерминированных машинах Тьюринга. Из процесса моделирования следует, что некоторые алгоритмические проблемы для рассматриваемых возвратных последовательностей могут быть даже EXPSPACE-полными. Таким образом, целочисленные полиномиальные возвратные последовательности с алгоритмической точки зрения представляют собой достаточно сложный объект.