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

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

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

Класс сложности

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

{\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]

Ссылки

^ Зоопарк сложности : Класс QP: Квазиполиномиальное время
^ Адлеман, Леонард М .; Померанс, Карл ; Румели, Роберт С. (1983), «О отличии простых чисел от составных чисел», Annals of Mathematics , 117 (1): 173–206, doi : 10.2307/2006975 , JSTOR 2006975
^ Агравал, Маниндра ; Каял, Нирадж ; Саксена, Нитин (2004), «ПРАЙМЫ находятся в P» (PDF) , Annals of Mathematics , 160 (2): 781–793, doi : 10.4007/annals.2004.160.781 , JSTOR 3597229
^ Кисфалуди-Бак, Шандор (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
^ Эппштейн, Дэвид ; Линкольн, Андреа; Уильямс, Вирджиния Василевска (2023), «Квазимолиномиальность наименьшего отсутствующего индуцированного подграфа», Журнал графовых алгоритмов и приложений , 27 (5): 329–339, arXiv : 2306.11185 , doi : 10.7155/jgaa.00625
^ Хазан, Элад; Краутгеймер, Роберт (2011), «Насколько сложно аппроксимировать лучшее равновесие Нэша?», SIAM Journal on Computing , 40 (1): 79–91, CiteSeerX 10.1.1.511.4422 , doi : 10.1137/090766991 , MR 2765712
^ Эйтер, Томас; Макино, Казухиса; Готтлоб, Георг (2008), «Вычислительные аспекты монотонной дуализации: краткий обзор», Discrete Applied Mathematics , 156 (11): 2035–2049, doi : 10.1016/j.dam.2007.04.017 , MR 2437000
^ Калуде, Кристиан С.; Джайн, Санджай; Хусаинов, Бахадыр; Ли, Вэй; Стефан, Франк (2022), «Определение игр на четность за квазиполиномиальное время», SIAM Journal on Computing , 51 (2): STOC17-152 – STOC17-188, doi : 10.1137/17M1145288 , hdl : 2292/31757 , MR 4413072
^ Премия IPEC Nerode , EATCS , получено 3 декабря 2023 г.
^ Пападимитриу, Христос Х .; Яннакакис, Михалис (1996), «Об ограниченном недетерминизме и сложности измерения VC», Journal of Computer and System Sciences , 53 (2): 161–170, doi : 10.1006/jcss.1996.0058 , MR 1418886
^ Мегиддо, Нимрод ; Вишкин, Узи (1988), «О поиске минимального доминирующего набора в турнире», Theoretical Computer Science , 61 (2–3): 307–316, doi : 10.1016/0304-3975(88)90131-4 , MR 0980249
^ Кларрайх, Эрика (14 января 2017 г.), «Изоморфизм графов снова побеждён» , журнал Quanta
^ Марк Лакенби объявляет о новом алгоритме распознавания узлов, работающем за квазиполиномиальное время , Математический институт Оксфордского университета , 03 февраля 2021 г. , получено 3 февраля 2021 г.
^ Реми, Ян; Стегер, Анжелика (2009), «Схема квазиполиномиальной аппроксимации по времени для триангуляции с минимальным весом», Журнал ACM , 56 (3), статья A15, doi : 10.1145/1516512.1516517
^ Бонне, Эдуард; Яннопулос, Панос; Ким, Ын Чжон ; Рзажевский, Павел; Сикора, Флориан (2018), «QPTAS и субэкспоненциальный алгоритм для максимальной клики на дисковых графах», в Спекманне, Беттина ; Тот, Чаба Д. (ред.), 34-й Международный симпозиум по вычислительной геометрии, SoCG 2018, 11–14 июня 2018 г., Будапешт, Венгрия , LIPics, vol. 99, Schloss Dagstuhl – Центр компьютерных наук Лейбница, стр. 12:1–12:15, doi : 10.4230/LIPICS.SOCG.2018.12
^ Браверман, Марк ; Кун-Ко, Янг; Вайнштейн, Омри (2015), «Приближение лучшего равновесия Нэша в ${\textstyle n^{o(\log n)}}$ -время нарушает гипотезу экспоненциального времени», в Индик, Петр (редактор), Труды 26-го ежегодного симпозиума ACM – SIAM по дискретным алгоритмам, SODA 2015, Сан-Диего, Калифорния, США, 4–6 января 2015 г. , стр. 970–982, дои : 10.1137/1.9781611973730.66

[zoo-1] Зоопарк сложности : Класс QP: Квазиполиномиальное время

[apr-2] Адлеман, Леонард М .; Померанс, Карл ; Румели, Роберт С. (1983), «О отличии простых чисел от составных чисел», Annals of Mathematics , 117 (1): 173–206, doi : 10.2307/2006975 , JSTOR 2006975

[aks-3] Агравал, Маниндра ; Каял, Нирадж ; Саксена, Нитин (2004), «ПРАЙМЫ находятся в P» (PDF) , Annals of Mathematics , 160 (2): 781–793, doi : 10.4007/annals.2004.160.781 , JSTOR 3597229

[hyperind-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

[missing-5] Эппштейн, Дэвид ; Линкольн, Андреа; Уильямс, Вирджиния Василевска (2023), «Квазимолиномиальность наименьшего отсутствующего индуцированного подграфа», Журнал графовых алгоритмов и приложений , 27 (5): 329–339, arXiv : 2306.11185 , doi : 10.7155/jgaa.00625

[planted-6] Хазан, Элад; Краутгеймер, Роберт (2011), «Насколько сложно аппроксимировать лучшее равновесие Нэша?», SIAM Journal on Computing , 40 (1): 79–91, CiteSeerX 10.1.1.511.4422 , doi : 10.1137/090766991 , MR 2765712

[mondual-7] Эйтер, Томас; Макино, Казухиса; Готтлоб, Георг (2008), «Вычислительные аспекты монотонной дуализации: краткий обзор», Discrete Applied Mathematics , 156 (11): 2035–2049, doi : 10.1016/j.dam.2007.04.017 , MR 2437000

[parity-8] Калуде, Кристиан С.; Джайн, Санджай; Хусаинов, Бахадыр; Ли, Вэй; Стефан, Франк (2022), «Определение игр на четность за квазиполиномиальное время», SIAM Journal on Computing , 51 (2): STOC17-152 – STOC17-188, doi : 10.1137/17M1145288 , hdl : 2292/31757 , MR 4413072

[nerode-9] Премия IPEC Nerode , EATCS , получено 3 декабря 2023 г.

[vcdim-10] Пападимитриу, Христос Х .; Яннакакис, Михалис (1996), «Об ограниченном недетерминизме и сложности измерения VC», Journal of Computer and System Sciences , 53 (2): 161–170, doi : 10.1006/jcss.1996.0058 , MR 1418886

[tourdom-11] Мегиддо, Нимрод ; Вишкин, Узи (1988), «О поиске минимального доминирующего набора в турнире», Theoretical Computer Science , 61 (2–3): 307–316, doi : 10.1016/0304-3975(88)90131-4 , MR 0980249

[graphiso-12] Кларрайх, Эрика (14 января 2017 г.), «Изоморфизм графов снова побеждён» , журнал Quanta

[unknot-13] Марк Лакенби объявляет о новом алгоритме распознавания узлов, работающем за квазиполиномиальное время , Математический институт Оксфордского университета , 03 февраля 2021 г. , получено 3 февраля 2021 г.

[mwt-14] Реми, Ян; Стегер, Анжелика (2009), «Схема квазиполиномиальной аппроксимации по времени для триангуляции с минимальным весом», Журнал ACM , 56 (3), статья A15, doi : 10.1145/1516512.1516517

[disk-clique-15] Бонне, Эдуард; Яннопулос, Панос; Ким, Ын Чжон ; Рзажевский, Павел; Сикора, Флориан (2018), «QPTAS и субэкспоненциальный алгоритм для максимальной клики на дисковых графах», в Спекманне, Беттина ; Тот, Чаба Д. (ред.), 34-й Международный симпозиум по вычислительной геометрии, SoCG 2018, 11–14 июня 2018 г., Будапешт, Венгрия , LIPics, vol. 99, Schloss Dagstuhl – Центр компьютерных наук Лейбница, стр. 12:1–12:15, doi : 10.4230/LIPICS.SOCG.2018.12

[nash-16] Браверман, Марк ; Кун-Ко, Янг; Вайнштейн, Омри (2015), «Приближение лучшего равновесия Нэша в ${\textstyle n^{o(\log n)}}$ -время нарушает гипотезу экспоненциального времени», в Индик, Петр (редактор), Труды 26-го ежегодного симпозиума ACM – SIAM по дискретным алгоритмам, SODA 2015, Сан-Диего, Калифорния, США, 4–6 января 2015 г. , стр. 970–982, дои : 10.1137/1.9781611973730.66

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]