Есть ли естественная проблема в квазиполиномиальном времени, но не в полиномиальном времени?

21

Ласло Бабаи недавно доказал, что проблема изоморфизма графа находится в квазиполиномиальном времени . См. Также его выступление в Чикагском университете, заметки о выступлениях Джереми Куна GLL, пост 1 , GLL, пост 2 , GLL, пост 3 .

Согласно теореме Ладнера, если , то не является пустым, т. содержит задачи, которые не являются ни ни полными. Однако язык, построенный Ладнером, является искусственным, а не естественной проблемой. Известно, что нет естественной проблемы в даже условно под . Но некоторые проблемы, как полагают, являются хорошими кандидатами для , такие как Факторинг целых чисел и GI.PNPNPINPPNPNPIPNPNPI

Мы можем думать, что с результатом Бабая, может быть алгоритм полиномиального времени для GI. Многие эксперты считают, что .NPQP=DTIME(npolylogn)

Есть некоторые проблемы, для которых мы знаем алгоритмы квазиполиномиального времени, но алгоритм полиномиального времени не известен. Такие проблемы возникают в алгоритмах приближения; известным примером является направленная задача дерева Штейнера, для которой существует алгоритм квазиполиномиального приближения по времени, достигающий отношения аппроксимации ( - число вершин). Тем не менее, показать существование такого алгоритма полиномиального времени является открытой проблемой.O(log3n)n

Мой вопрос:

Известны ли нам какие-либо естественные проблемы, которые есть в но не в ?QPP

Рупей Сюй
источник
6
Разве теорема о временной иерархии не гарантирует существование таких проблем?
РБ
@RB Спасибо за ваш ответ. Вы верите, что временная иерархия может рухнуть? Я ожидаю несколько естественных примеров, которые можно решить за квазиполиномиальное время, но не за полиномиальное время.
Рупей Сюй
3
@ RupeiXu Это известный факт, что он не может разрушиться.
Том ван дер Занден
3
@RupeiXu Ваш вопрос будет интересным, если вы ищете естественную проблему.
Мухаммед Аль-Туркистани
3
Минимальный доминирующий сет на турнирах в QP. Оно не может быть в P, если ETH не ложно.
Мухаммед Аль-Туркистани

Ответы:

25

На самом деле, было довольно много недавних работ по доказательству нижней границы квазиполиномиального времени выполнения для вычислительных задач, в основном основанной на гипотезе экспоненциального времени. Вот некоторые результаты для проблем, которые я считаю вполне естественными (все результаты, приведенные ниже, зависят от ETH):

  • Ааронсон, Импальяццо и Мошковиц [1] показывают квазиполиномиальную нижнюю оценку времени для задач удовлетворения плотных ограничений (CSP). Обратите внимание, что способ определения CSP в этой статье позволяет домену быть полиномиально большим, так как известно, что случай, когда домен маленький, имеет PTAS.

  • Браверман, Ко и Вайнштейн [2] доказывают квазиполиномиальную нижнюю границу времени для нахождения -best -приближенного равновесия Нэша, которое соответствует алгоритму Липтона и др. [3].ϵεε

  • Браверман, Ко, Рубинштейн и Вайнштейн [4] показывают квазиполиномиальную нижнюю границу времени для аппроксимации наиболее плотного -подграфа с совершенной полнотой (т. Е. С учетом графа, содержащего -клик, находит подграф размера k, который равен ( 1 - ε ) -плотная для некоторых малых постоянная е ). Опять же, существует квазиполиномиальный алгоритм времени для задачи (Фейге и Сельцер [5]).кККК(1-ε)ε

Ссылки

  1. AM с несколькими Мерлинами. В вычислительной сложности (CCC), 2014 IEEE 29-я конференция, стр. 44–55, июнь 2014.

  2. Марк Браверман, Янг Кун Ко и Омри Вайнштейн. Аппроксимация наилучшего равновесия Нэша в -time перерывов экспоненциальных гипотезы времени. В материалах двадцать шестого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, SODA '15, стр. 970–982. СИАМ, 2015.Nо(LограммN)

  3. Ричард Дж. Липтон, Евангелос Маркакис и Араньяк Мехта. Играть в большие игры, используя простые стратегии. В материалах 4-й конференции ACM по электронной торговле, EC '03, стр. 36–41, Нью-Йорк, штат Нью-Йорк, США, 2003 г. ACM.

  4. Марк Браверман, Янг Кун-Ко, Авиад Рубинштейн и Омри Вайнштейн. ETH твердость для Densest- Subgraph с идеальной полнотой. Электронный коллоквиум по вычислительной сложности (ECCC), 22:74, 2015.К

  5. У. Фейге и М. Зельцер. О самых плотных задачах -подграфа. Технический отчет, 1997.К

Пасин Мануранги
источник
22

Мегиддо и Vishkin доказали , что минимальный набор доминирующего в турнирах в . Они показали, что в турнирно-доминирующем наборе используется алгоритм P-времени, если SAT имеет субэкспоненциальный алгоритм времени. Следовательно, проблема доминирующего турнира не может быть в P, если ETH не ложно.Qпп

Очень интересно отметить, что гипотеза экспоненциального времени одновременно подразумевает, что множество, доминирующее в турнире, не может иметь алгоритмы полиномиального времени и не может быть -завершеннымNп . Другими словами, ETH подразумевает, что сет доминирующего турнира находится в -интермедиате.Nп

Woeginger предлагает потенциальную задачу, разрешимую в квазиполиномиальное время, и, вероятно, не имеет алгоритмов полиномиального времени: учитывая целых чисел, вы можете выбрать log n из них, которые складываются в 0 ?NжурналN0

Мухаммед Аль-Туркистани
источник
10

Вычисление размерности VC кажется маловероятным за полиномиальное время, но имеет алгоритм квазиполиномиального времени.

Кроме того, кажется, что трудно обнаружить установленную клику размером в случайном графе, но ее можно найти за квазиполиномиальное время; хотя природа этой проблемы обещания несколько отличается от других упомянутых.О(журналN)

Джо Бебель
источник
7

Если гипотеза об экспоненциальном времени верна (или даже более слабые версии), то 3SAT не может быть решена для случаев с числом переменных в поликлоге за полиномиальное время. Конечно, квазиполиномиальное время может легко разрешить такие случаи.

T(N)*журналNT(N)T(N)

Сариэль Хар-Пелед
источник
4

Недавно было показано, что игры «Solity Parity» в QP: https://www.comp.nus.edu.sg/~sanjay/paritygame.pdf

μ

NпсоNпUпсоUп

Тем не менее, недавняя статья выше сделала значительный скачок к QP. Пока неизвестно, есть ли эти игры в P.

Shaull
источник
2

В Классических алгоритмах, затухании корреляции и комплексных нулях функций разбиения квантовых систем многих тел Арама Харроу, Саида Мехрабана и Мехди Сулейманифара

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

представлено.

Здесь мало что можно сказать о «но не за полиномиальное время» части вопроса. Возможно даже, что алгоритм полиномиального времени будет найден позже, учитывая историю предыдущих работ, см. Ниже.

Как «оценка функции разбиения» связана с алгоритмами аппроксимации? Предыдущая работа (стр. 11):

В последнее время существует концептуально иной подход к оценке функции разбиения, который лежит в основе этой работы. Этот подход рассматривает функцию разбиения как многомерный многочлен и использует усеченное разложение Тейлора, чтобы расширить решение в простой для вычисления точке на нетривиальный режим параметров. С момента своего появления [Bar16a] этот метод использовался для получения детерминированных алгоритмов для различных интересных задач, таких как ферромагнитная и антиферромагнитная модели Изинга [LSS19b, PR18] на ограниченных графах.

включает

[LSS19b] Цзинчэн Лю, Алистер Синклер и Пиюш Шривастава. Функция разбиения Изинга: нули и детерминированная аппроксимация. Журнал статистической физики, 174 (2): 287–315, 2019. arXiv: 1704.06493

который упоминает следующее в этом разделе о связанной работе:

Параллельно с этим Барвинок инициировал изучение тейлоровской аппроксимации логарифма функции распределения, что привело к квазиполиномиальным алгоритмам аппроксимации по времени для различных задач подсчета [6, 7, 9, 10]. Совсем недавно Patel и Regts [41] показали, что для нескольких моделей, которые могут быть записаны как индуцированные суммы подграфа, на самом деле можно получить FPTAS из этого подхода.

[41] В. Патель и Г. Регтс. Детерминированные алгоритмы аппроксимации полиномиального времени для функций разбиения и полиномов графов. SIAM J. Comput., 46 (6): 1893–1919, декабрь 2017. arXiv: 1607.01167

В заключение, «оценка функции разбиения» тесно связана с алгоритмами аппроксимации, и для квазиполиномиальных алгоритмов аппроксимации по времени для множества задач подсчета были найдены некоторые из этих FPTAS. Таким образом, в целом, этот класс проблем, связанных с функцией разделения, кажется, производит квазиполиномиальные алгоритмы аппроксимации по времени, но часто более поздние улучшения достигают полиномиального времени.

Томас Климпел
источник