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

В теории сложности вычислений и анализе алгоритмов говорят, что алгоритм использует квазиполиномиальное время, если его временная сложность квазиполиномиально ограничена . То есть должна существовать такая константа, чтобы время работы алгоритма в наихудшем случае на входных данных размера имело верхнюю границу вида ${\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. Зоопарк сложности : Класс 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 (неактивен в 2024–2007 гг.) -29){{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), «Вычислительные аспекты монотонной дуализации: краткий обзор», Discrete Applied Mathematics , 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 , получено 3 декабря 2023 г.
10. Пападимитриу, Христос Х .; Яннакакис, Михалис (1996), «Об ограниченном недетерминизме и сложности измерения VC», Journal of Computer and System Sciences , 53 (2): 161–170, doi : 10.1006/jcss.1996.0058 , MR  1418886
11. Мегиддо, Нимрод ; Вишкин, Узи (1988), «О поиске минимального доминирующего набора в турнире», Theoretical Computer Science , 61 (2–3): 307–316, doi : 10.1016/0304-3975(88)90131-4, MR  0980249
12. Кларрайх, Эрика (14 января 2017 г.), «Изоморфизм графов снова побежден», Quanta Magazine
13. Марк Лакенби объявляет о новом алгоритме распознавания узлов, который работает за квазиполиномиальное время, Математический институт Оксфордского университета , 3 февраля 2021 г. , получено 3 февраля 2021 г.
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. Браверман, Марк ; Кун-Ко, Янг; Вайнштейн, Омри (2015), «Приближение наилучшего равновесия Нэша во времени нарушает гипотезу экспоненциального времени», в Индик, Петр (редактор), Труды 26-го ежегодного симпозиума ACM – SIAM по дискретным алгоритмам, SODA 2015, Сан-Диего , Калифорния, США, 4–6 января 2015 г. , стр. 970–982, doi : 10.1137/1.9781611973730.66. ${\textstyle n^{o(\log n)}}$