При разработке алгоритма для новой задачи, если я не смогу найти алгоритм полиномиального времени через некоторое время, я мог бы попытаться доказать, что он NP-сложный. Если мне это удастся, я объяснил, почему я не смог найти алгоритм полиномиального времени. Не то, чтобы я точно знал, что P! = NP, просто это лучшее, что можно сделать с текущими знаниями, и на самом деле все согласны с тем, что P! = NP.
Точно так же, скажем, я нашел решение за полиномиальное время для некоторой проблемы, но время выполнения равно . После многих усилий я не прогрессирую в улучшении этого. Так что вместо этого я мог бы попытаться доказать, что это 3SUM-hard вместо этого. Обычно это удовлетворительное положение дел, не потому, что я убежден, что 3SUM действительно требует Θ ( n 2 ) времени, а потому, что это современное состояние, и многие умные люди пытались его улучшить, и не удалось. Так что я не виноват, что это лучшее, что я могу сделать.
В таких случаях лучшее, что мы можем сделать, - это получить результат твердости вместо действительной нижней границы, поскольку у нас нет суперлинейных нижних оценок для машин Тьюринга для задач в NP.
Существует ли единообразный набор проблем, которые можно использовать для всех полиномиальных периодов времени? Например, если я хочу доказать, что маловероятно, что какая-то проблема имеет алгоритм лучше, чем , есть ли проблема X такая, что я могу показать, что она X-трудная, и оставить все как есть?
Обновление : этот вопрос изначально задавался для семейства проблем. Поскольку семейства проблем не так много, и этот вопрос уже получил отличные примеры отдельных трудных проблем, я смягчаю вопрос о любой проблеме, которую можно использовать для получения результатов твердости за полиномиальное время. Я также добавляю награду к этому вопросу, чтобы поощрить больше ответов.
источник
Ответы:
Да, самый известный алгоритм для -SUM выполняется за O ( n ⌈ k / 2 ⌉ ) времени, поэтому вполне возможно, что вы могли бы утверждать, что некоторая проблема n 7 трудна, потому что если она находится в n 6.99, то вы можете решить 14 - СУММА быстрее.k O(n⌈k/2⌉) n7 n6.99 14
источник
источник
Дж. Эриксон, С. Хар-Пелед и Д. М. Маунт, О проблеме наименьшего срединного квадрата, дискретной и вычислительной геометрии, 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
источник
источник