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

В теории сложности вычислений и анализе алгоритмов говорят, что алгоритм занимает квазиполиномиальное время , если его временная сложность квазиполиномиально ограничена . То есть должна существовать константа, такая, что худшее время выполнения алгоритма на входах размера имеет верхнюю границу вида ${\displaystyle c}$ ${\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]

Ссылки

1. Complexity Zoo : Класс QP: Квазиполиномиальное время
2. Адлеман, Леонард М.; Померанс , Карл ; Румели, Роберт С. (1983), «О различении простых чисел от составных», Annals of Mathematics , 117 (1): 173–206, doi :10.2307/2006975, JSTOR  2006975
3. Агравал, Маниндра ; Каял, Нирадж ; Саксена, Нитин (2004), «ПРАЙМЫ находятся в P» (PDF) , Annals of Mathematics , 160 (2): 781–793, doi : 10.4007/annals.2004.160.781, JSTOR  3597229
4. Кишфалуди-Бак, Шандор (2020), «Гиперболические графы пересечений и (квази)полиномиальное время», в Чавла, Шучи (ред.), Труды 31-го ежегодного симпозиума ACM–SIAM по дискретным алгоритмам, SODA 2020, Солт-Лейк-Сити, Юта, США, 5–8 января 2020 г. , стр. 1621–1638, arXiv : 1812.03960 , doi : 10.1137/1.9781611975994.100, ISBN 978-1-61197-599-4
5. Эппштейн, Дэвид ; Линкольн, Андреа; Уильямс, Вирджиния Василевска (2023), «Квазиполиномиальность наименьшего отсутствующего индуцированного подграфа», Журнал графовых алгоритмов и приложений , 27 (5): 329–339, arXiv : 2306.11185 , doi : 10.7155/jgaa.00625 (неактивен 29 июля 2024 г.){{citation}}: CS1 maint: DOI неактивен по состоянию на июль 2024 г. ( ссылка )
6. Хазан, Элад; Краутгеймер, Роберт (2011), «Насколько сложно приблизиться к наилучшему равновесию Нэша?», SIAM Journal on Computing , 40 (1): 79–91, CiteSeerX 10.1.1.511.4422 , doi :10.1137/090766991, MR  2765712 
7. Эйтер, Томас; Макино, Казухиса; Готтлоб, Георг (2008), «Вычислительные аспекты монотонной дуализации: краткий обзор», Дискретная прикладная математика , 156 (11): 2035–2049, doi : 10.1016/j.dam.2007.04.017 , MR  2437000
8. Калуд, Кристиан С.; Джейн, Санджай; Хуссаинов, Бахадыр; Ли, Вэй; Стефан, Франк (2022), «Решение игр с четностью за квазиполиномиальное время», SIAM Journal on Computing , 51 (2): STOC17-152–STOC17-188, doi : 10.1137/17M1145288, hdl : 2292/31757 , MR  4413072
9. Премия IPEC Nerode, EATCS , получено 03.12.2023
10. Пападимитриу, Христос Х.; Яннакакис , Михалис (1996), «Об ограниченном недетерминизме и сложности измерения VC», Журнал компьютерных и системных наук , 53 (2): 161–170, doi : 10.1006/jcss.1996.0058 , MR  1418886
11. Мегиддо, Нимрод ; Вишкин, Узи (1988), «О поиске минимального доминирующего набора в турнире», Теоретическая информатика , 61 (2–3): 307–316, doi :10.1016/0304-3975(88)90131-4, MR  0980249
12. Кларрайх, Эрика (14 января 2017 г.), «Изоморфизм графов побеждён — снова», Quanta Magazine
13. Марк Лакенби анонсирует новый алгоритм распознавания неразветвленных узлов, работающий за квазиполиномиальное время, Математический институт Оксфордского университета , 2021-02-03 , получено 2021-02-03
14. Реми, Ян; Стегер, Анжелика (2009), «Квазиполиномиальная схема аппроксимации времени для триангуляции с минимальным весом», Журнал ACM , 56 (3), Статья A15, doi : 10.1145/1516512.1516517
15. Бонне, Эдуард; Яннопулос, Панос; Ким, Ын Чжон ; Рзажевский, Павел; Сикора, Флориан (2018), «QPTAS и субэкспоненциальный алгоритм для максимальной клики на дисковых графах», в Спекманне, Беттина ; Тот, Чаба Д. (ред.), 34-й Международный симпозиум по вычислительной геометрии, SoCG 2018, 11–14 июня 2018 г., Будапешт, Венгрия , LIPics, vol. 99, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, стр. 12:1–12:15, doi : 10.4230/LIPICS.SOCG.2018.12
16. Braverman, Mark ; Kun-Ko, Young; Weinstein, Omri (2015), «Аппроксимация наилучшего равновесия Нэша за -время нарушает гипотезу экспоненциального времени», в Indyk, Piotr (ред.), Труды 26-го ежегодного симпозиума ACM–SIAM по дискретным алгоритмам, SODA 2015, Сан-Диего, Калифорния, США, 4–6 января 2015 г. , стр. 970–982, doi :10.1137/1.9781611973730.66 ${\textstyle n^{o(\log n)}}$