Квазиполиномиальное время

В теории сложности вычислений и анализе алгоритмов говорят, что алгоритм занимает квазиполиномиальное время , если его временная сложность квазиполиномиально ограничена . То есть должна существовать константа, такая, что худшее время выполнения алгоритма на входах размера имеет верхнюю границу вида${\displaystyle с}$${\displaystyle n}$$${\displaystyle 2^{O{\bigl (}(\log n)^{c}{\bigr)}}.}$$

Задачи принятия решений с помощью алгоритмов с квазиполиномиальным временем являются естественными кандидатами на звание NP-промежуточных , поскольку не имеют ни полиномиального времени , ни, скорее всего, NP-трудны .

Класс сложности QP состоит из всех задач, имеющих квазиполиномиальные алгоритмы времени. Он может быть определен в терминах DTIME следующим образом. ^[1]

${\displaystyle {\mathsf {QP}}=\bigcup _{c\in \mathbb {N} }{\mathsf {DTIME}}\left(2^{(\log n)^{c}}\right)}$

Ранним примером алгоритма с квазиполиномиальным временем был тест на простоту Адлемана–Померанса–Румели ^[2] ; однако впоследствии было показано , что для задачи проверки того, является ли число простым, существует алгоритм с полиномиальным временем — тест на простоту AKS ^[3] .

В некоторых случаях можно доказать, что квазиполиномиальные временные границы являются оптимальными при гипотезе экспоненциального времени или связанном предположении вычислительной сложности . Например, это справедливо для нахождения наибольшего непересекающегося подмножества набора единичных дисков в гиперболической плоскости , ^[4] и для нахождения графа с наименьшим количеством вершин, который не появляется как индуцированный подграф данного графа. ^[5]

Другие задачи, для решения которых наиболее известный алгоритм требует квазиполиномиального времени, включают:

• Задача о посаженной клике , заключающаяся в определении того, был ли изменен случайный граф путем добавления ребер между всеми парами подмножества его вершин. ^[6]
• Монотонная дуализация , несколько эквивалентных задач преобразования логических формул между конъюнктивной и дизъюнктивной нормальной формой, перечисление всех минимальных попадающих множеств семейства множеств или перечисление всех минимальных покрытий множеств семейства множеств, со сложностью времени, измеряемой в объединенном размере входных и выходных данных. ^[7]
• Игры на четность , включающие передачу токенов по ребрам цветного ориентированного графа. ^[8] Статья, дающая квазиполиномиальный алгоритм для этих игр, выиграла премию Нерода 2021 года . ^[9]
• Вычисление размерности Вапника–Червоненкиса семейства множеств . ^[10]
• Нахождение наименьшего доминирующего множества в турнире , подмножества вершин турнира, имеющего по крайней мере одно направленное ребро ко всем остальным вершинам. ^[11]

Задачи, для которых был анонсирован, но не полностью опубликован квазиполиномиальный алгоритм, включают:

• Проблема изоморфизма графов , определяющая, можно ли сделать два графа равными друг другу путем переименования их вершин, была анонсирована в 2015 году и обновлена ​​в 2017 году Ласло Бабаем . ^[12]
• Проблема распутывания узла , распознающая, описывает ли диаграмма узла распутывание узла , анонсированная Марком Лакенби в 2021 году. ^[13]

Квазиполиномиальное время также использовалось для изучения алгоритмов аппроксимации . В частности, схема аппроксимации с квазиполиномиальным временем (QPTAS) является вариантом схемы аппроксимации с полиномиальным временем , время выполнения которой является квазиполиномиальным, а не полиномиальным. Задачи с QPTAS включают триангуляцию с минимальным весом ^[14] и поиск максимальной клики на графе пересечений дисков. ^[15]

Более того, проблема нахождения приблизительного равновесия Нэша имеет QPTAS, но не может иметь PTAS в соответствии с гипотезой экспоненциального времени. ^[16]