Проблемы, которые можно использовать, чтобы показать результаты твердости за полиномиальное время

58

При разработке алгоритма для новой задачи, если я не смогу найти алгоритм полиномиального времени через некоторое время, я мог бы попытаться доказать, что он NP-сложный. Если мне это удастся, я объяснил, почему я не смог найти алгоритм полиномиального времени. Не то, чтобы я точно знал, что P! = NP, просто это лучшее, что можно сделать с текущими знаниями, и на самом деле все согласны с тем, что P! = NP.

Точно так же, скажем, я нашел решение за полиномиальное время для некоторой проблемы, но время выполнения равно . После многих усилий я не прогрессирую в улучшении этого. Так что вместо этого я мог бы попытаться доказать, что это 3SUM-hard вместо этого. Обычно это удовлетворительное положение дел, не потому, что я убежден, что 3SUM действительно требует Θ ( n 2 ) времени, а потому, что это современное состояние, и многие умные люди пытались его улучшить, и не удалось. Так что я не виноват, что это лучшее, что я могу сделать.O(n2)Θ(n2)

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

Существует ли единообразный набор проблем, которые можно использовать для всех полиномиальных периодов времени? Например, если я хочу доказать, что маловероятно, что какая-то проблема имеет алгоритм лучше, чем , есть ли проблема X такая, что я могу показать, что она X-трудная, и оставить все как есть?O(n7)

Обновление : этот вопрос изначально задавался для семейства проблем. Поскольку семейства проблем не так много, и этот вопрос уже получил отличные примеры отдельных трудных проблем, я смягчаю вопрос о любой проблеме, которую можно использовать для получения результатов твердости за полиномиальное время. Я также добавляю награду к этому вопросу, чтобы поощрить больше ответов.

Робин Котари
источник
5
Страница maven.smith.edu/~orourke/TOPP/P11.html обобщает некоторые результаты о нижних (и верхних) границах 3SUM и связанных проблемах и заслуживает прочтения.
Цуёси Ито
2
Отсутствие суперлинейных нижних границ относится к ТМ с минимум двумя лентами, не так ли? Я помню, как читал где-то, что проверка палиндрома на однотонной ТМ имеет нижнюю границу квадратичного времени. Когда мы говорим о нижних границах внутри , типа Ω ( n i ) и Ω ( n i + 1 ) , все еще нормально предположить, что точная модель TM не имеет большого значения? PΩ(ni)Ω(ni+1)
gphilip
3
Не по теме: Робин, Цуёси, спасибо за представление семейства нижних границ 3SUM: я никогда не слышал о них раньше.
gphilip
2
@Tsuyoshi: Спасибо за информацию. Это хороший опрос на эту тему: cs.mcgill.ca/~jking/papers/3sumhard.pdf . @gphilip: Меня недавно познакомили с этой проблемой некоторые вычислительные геометры. Я думаю, что это очень хорошо известно в этой области.
Робин Котари
Отличный вопрос Не могли бы вы уточнить, что вы подразумеваете под «униформой»: хотите ли вы ограничить объем предварительной обработки параметра?
Андрас Саламон

Ответы:

35

Да, самый известный алгоритм для -SUM выполняется за O ( n k / 2 ) времени, поэтому вполне возможно, что вы могли бы утверждать, что некоторая проблема n 7 трудна, потому что если она находится в n 6.99, то вы можете решить 14 - СУММА быстрее.kO(nk/2)n7n6.9914

kkk2kO(n2)n2kk0O(nk/2ε)kO(nk2ε)2k2kk

kO(logn)O(n2)3kW\[1\]kW\[2\]

3TIME[n2]TIME[n2]33O(logn)3PNPn2n2

Райан Уильямс
источник
4
O(n2.376)Θ(nk)
kkkO(nk/2)kkO(nk/2)
n2
@ Райан: Вы правы, они одинаковы. Хотя, с k-SUM, по крайней мере, у нас есть доказательства в более слабых моделях, что предполагаемая оценка верна. Я не знаю ни одного аргумента, который бы предполагал, что 3-клика не должна решаться быстрее, чем умножение матриц.
Робин Котари
nf(k)f(k)=Θ(k)
14

Ω(n3)

Михай
источник
2
Как насчет диаметра графика? А еще лучше сделайте решение проблемы «Диаметр не менее k?». Насколько я знаю, это имеет то преимущество, что не имеет явной суперлинейной границы.
Рафаэль
9

dO(nd)ndd+1

(d+1)kΩ(nd/2+1)d3

Дж. Эриксон, С. Хар-Пелед и Д. М. Маунт, О проблеме наименьшего срединного квадрата, дискретной и вычислительной геометрии, 36, 593-607, 2006. http://www.cs.umd.edu/~mount/Papers /dcg06-lms.pdf

Дж. Эриксон и Р. Зайдель. Лучше нижние оценки при обнаружении единичных и сферических вырождений. Дискретный компьютер Geom., 13: 41–57, 1995. http://compgeom.cs.uiuc.edu/~jeffe/pubs/degen.html

Дж. Эриксон. Новые нижние оценки для задач выпуклой оболочки в нечетных измерениях. SIAM J. Comput., 28: 1198–1214, 1999. http://compgeom.cs.uiuc.edu/~jeffe/pubs/convex.html

Гильерме Д. да Фонсека
источник
Мне нравится этот ответ, но не могли бы вы объяснить? Почему в это верят?
Аарон Стерлинг
8

Θ(n4/3)nn

Jeffε
источник
7
Есть ли негеометрические задачи, которые сводятся к проблеме Хопкрофта?
Суреш Венкат
Я решил назначить награду за этот ответ, потому что я никогда не слышал об этой проблеме раньше.
Робин Котари