Каковы отношения между этими гипотезами в теории детальной сложности?

23

Теория сложности, с помощью таких понятий, как NP-полнота, различает вычислительные задачи, которые имеют относительно эффективные решения, и те, которые трудноразрешимы. «Мелкозернистая» сложность призвана уточнить это качественное различие в количественном руководстве относительно точного времени, необходимого для решения проблем. Более подробную информацию можно найти здесь: http://simons.berkeley.edu/programs/complexity2015

Вот несколько важных гипотез:

ETH: - требует времени для некоторого .S A T 2 δ n δ > 03SAT2δnδ>0

SETH: для каждого существует такое , что - для переменных, предложений не могут быть решены за времени.k k S A T n m 2 ( 1 - ε ) n p o l y mε>0kkSATnm2(1ε)n poly m

Известно, что SETH сильнее, чем ETH, и оба они сильнее, чем , и оба сильнее, чем .F T P W [ 1 ]PNPFTPW[1]

Четыре других важных предположения:

  1. Гипотеза 3SUM: 3SUM для целых чисел в требует времени{ - n 3 , , n 3 } n 2 - o ( 1 )n{n3,,n3}n2o(1)

  2. Гипотеза О. В. Ортогональные векторы на векторах требуют времени.n 2 - o (nn2o(1)

  3. Гипотеза APSP: кратчайший путь всех пар на узлах и битовых весах требует времени.O ( log n ) n 3 - o ( 1 )nO(logn)n3o(1)

  4. Гипотеза BMM: Любой «комбинаторный» алгоритм для умножения булевой матрицы требует времени.n3o(1)

Известно, что SETH подразумевает гипотезу О.В. (Райан Вилламс, 2004). Помимо доказательства Райана, что SETH гипотезу О. В., нет других сокращений, относящихся к известным гипотезам.

Мой вопрос: знаете ли вы другие связанные гипотезы или предположения в этой области? Каковы отношения между ними?

Подтверждение: приведенные результаты взяты из слайдов Вирджинии Васильевской, Уильямс, она также дала мне частичные ответы на этот вопрос.

Ссылка на слайды: http://theory.stanford.edu/~virgi/overview.pdf

Рупей Сюй
источник
Привет, Рупей, я работал над различными задачами о достижимости графа и ограничениях, которые связаны с очень хорошим списком проблем мелкозернистой сложности, о которых ты упомянул. Если вам это интересно, напишите мне на электронную почту, и мы могли бы поговорить когда-нибудь. Я рад видеть других, кто интересуется мелкозернистой сложностью на stackexchange. :)
Майкл Вехар
3
Тривиальное сокращение: «комбинаторный» субкубический APSP подразумевает «комбинаторный» субкубический BMM. Для 3SUM см. Взаимосвязь между связанными проблемами на странице 14 этого слайда cs.uwaterloo.ca/~tmchan/talks/bsg_stoc_talk.pdf . Что касается BMM, см. Раздел G этой статьи теорией.stanford.edu/~virgi/tria-mmult-conf.pdf . Для APSP есть много работ Вирджинии, показывающих субкубическую эквивалентность.
Thatchaphol
1
@ Thatchaphol, спасибо за добрый обмен!
Рупей Сюй

Ответы:

15

Это недавняя статья, в которой представлена ​​недетерминированная гипотеза сильного экспоненциального времени (NSETH), которая является расширением SETH.

NSETH: для каждого существует такое k , что k -DNF-TAUT не может быть решено за недетерминированное время 2 ( 1 - ϵ ) n .ϵ>0kk2(1ϵ)n

NSETH подразумевает SETH. Если NSETH истинно, то у некоторых задач нет нижних границ SETH (потому что они имеют недетерминированные алгоритмы быстрее, чем детерминированные алгоритмы).

Эта статья также представила неоднородную недетерминированную гипотезу сильного экспоненциального времени (NUNSETH), гипотезу, более сильную, чем NSETH и SETH.

NUNSETH: для каждого существует такое k , что k -DNF-TAUT не может быть распознано недетерминированными семействами цепей размером 2 ( 1 - ϵ ) n .ϵ>0kk2(1ϵ)n

Rosetta
источник
1
Спасибо за новаторскую работу! Райан Уильямс считает, что СЕТ является ложным. Как вы думаете, NSETH это правда?
Рупей Сюй
2
В этой статье отмечается, что Райан на самом деле показал, что версия МА SETH является ложной, что, по-видимому, предполагает, что NSETH вряд ли будет правдой. Тем не менее, в некотором смысле, суть в том, что для того, чтобы показать связь между некоторыми из этих других гипотез, вам сначала нужно добиться прогресса в опровержении NSETH.
палиндром
8

Другая интересная гипотеза - это твердость клика для фиксированного k (см. Здесь ).kk

Это не совсем те отношения, которые вы ищете, но была интересная статья по FOCS, показывающая, что естественная проблема под названием «Сопоставление треугольников» трудна при любой гипотезе SETH, 3SUM или APSP (см. Здесь ). В настоящее время неизвестно, подразумевают ли какие-либо из этих трех гипотез друг друга каким-либо интересным образом - это один из главных открытых вопросов детальной сложности.

GMB
источник
1
Спасибо, Грег! Моя первоначальная мотивация для публикации этого вопроса здесь состоит в том, чтобы собрать все существующие результаты в этой области, например, хорошие коллекции в информационном бюллетене «Параметризованная сложность» fpt.wikidot.com/…
Rupei Xu
k
1

O(n2ϵ)

O(n2ϵ)

kno(k)NLP

В этой связи следует также отметить, что существует известная существенная связь между конструкциями DFA и вычислениями расстояния Левенштейна, например, в этой статье.

ВЗН
источник
1
Добавил несколько небольших исправлений в ваш пост VZN. Это было мило с твоей стороны упомянуть меня. Я очень увлечен проблемой пересечения DFA и, надеюсь, в будущем у меня будет еще много дел. :)
Майкл Вехар