О некоторых алгоритмах квазиполиномиального времени - Селиверстов, Александр Владиславович (Компьютерные инструменты в образовании, 2021)
С древности алгоритмы неразрывно связаны с математикой. Однако самостоятельное развитие теория алгоритмов получила лишь в первой половине ХХ века. Начальный период был связан с открытием как неразрешимых, так и очень трудных проблем. Например, в 1927 году Габриэль Судан опубликовал первый пример вычислимой функции, которая доказуемо не служит примитивно рекурсивной. Практическое значение асимптотических оценок вычислительной сложности стало очевидным лишь во второй половине ХХ века. Мы рассматриваем некоторые хорошо известные задачи принятия решений, которые можно решить за квазиполиномиальное время, то есть задачи, предположительно принадлежащие к промежуточному классу между полиномиальным и экспоненциальным временем. Коллекция включает в себя проверку изоморфности, вычисление исхода игры на чётность и (обоснованную в предположении справедливости обобщенной гипотезы Римана) факторизацию многочленов от одной переменной над конечными полями. Также представлены некоторые технические результаты, которые могут быть использованы для создания новых алгоритмов квазиполиномиального времени.