Я хотел бы начать с вопроса, говоря, что я программист, и у меня нет большого опыта в теории сложности.
Одна вещь, которую я заметил, состоит в том, что, хотя многие проблемы являются NP-полными, когда они распространяются на проблемы оптимизации, некоторые из них гораздо сложнее приблизить, чем другие.
Хороший пример - TSP. Несмотря на то, что все виды TSP являются NP-полными, соответствующие задачи оптимизации легче и легче аппроксимировать с последовательными упрощениями. Общий случай является NPO-полным, метрический случай - APX-полным, а евклидовый случай фактически имеет PTAS.
Это кажется мне нелогичным, и мне интересно, есть ли причина для этого.
Ответы:
Одна из причин того, что мы видим различные сложности аппроксимации для NP-полных задач, состоит в том, что необходимые условия для NP-полных представляют собой очень грубую меру сложности задачи. Возможно, вы знакомы с основным определением проблемы быть NP-полным:Π
Рассмотрим условие 2: все, что требуется, это то, что мы можем взять и превратить его в некоторый y, который сохраняет «однобитный» ответ да / нет. Нет никаких условий, например, относительно размера свидетелей относительно «да» или «нет» (то есть размера решения в контексте оптимизации). Таким образом, единственная используемая мера - это общий размер входных данных, который лишь очень слабо влияет на размер решения. Так что это довольно «легко» превратить £ , в П .Икс Y Ξ Π
Мы можем увидеть разницу в различных NP-полных задачах, взглянув на сложность некоторых простых алгоритмов. -Цвет имеет грубую силу O ( k n ) (где n - размер ввода). Для k- доминирующего множества подход грубой силы принимает O ( n k ) . По сути, это лучшие точные алгоритмы, которые у нас есть. Однако k- Vertex Cover имеет очень простое значение O ( 2 k n c ).К O ( кN) N К O ( nК) К O ( 2КNс) Алгоритм (выберите ребро, ветвь, в которую нужно включить конечную точку, отметьте все покрытые, продолжайте движение, пока у вас не останется немаркированных ребер или пока вы не достигнете своего бюджета и bactrack). При многократном сокращении за полиномиальное время (сокращение Карпа, то есть то, что мы делаем в условии 2 выше), эти проблемы эквивалентны.К
Когда мы начинаем приближаться к сложности с помощью чуть более деликатных инструментов (сложности аппроксимации, параметризованной сложности, любых других, о которых я не могу думать), используемые нами сокращения становятся более строгими или, скорее, более чувствительными к структуре решения, и различия начинают появляться; Покрытие Vertex (как упомянул Ювал) имеет простую 2-аппроксимацию (но не имеет FPTAS, если не разваливаются некоторые классы сложности), k- Доминирующий Set имеет ( 1 + log n ) -приближающий алгоритм (но нет ( c log n ) -приближение для некоторого c > 0К К ( 1 + журналн ) ( c журналн ) с > 0 ), и приближение не имеет никакого смысла для прямой версии -Coloring.К
источник
Один из способов рассмотреть разницу между версией решения и версией оптимизации - рассмотреть разные версии оптимизации одной и той же версии решения. Возьмем, к примеру, задачу MAX-CLIQUE, которую очень трудно аппроксимировать с точки зрения обычного параметра - размера клики. Если мы изменим параметр оптимизации на логарифм размера клики, мы получим проблему с алгоритмом аппроксимации . Если изменить параметр оптимизации для 1 / 2 + к / п , где к является размер клики, то мы можем получить O ( 1 )O ( журналн ) 1 / 2 + к / п К O ( 1 ) алгоритм приближения.
Эти примеры не полностью составлены. Проблемы MAX-INDEPENDENT-SET (эквивалентные MAX-CLIQUE) и MIN-VERTEX-COVER тесно связаны - дополнением к независимому набору является покрытие вершин. Но в то время как первое трудно приблизить, второе имеет простое 2-приближение.
Редукции, показывающие NP-твердость данной проблемы, иногда можно использовать для отображения твердости аппроксимации, но это не всегда так - это зависит от редукции. Например, сокращение от MAX-INDEPENDENT-SET до MIN-VERTEX-COVER не подразумевает сложность аппроксимации последней задачи, которую гораздо легче приблизить, чем первую.
Подводя итог, NP-твердость является лишь одним аспектом проблемы. Твердость аппроксимации - это другой аспект, и он сильно зависит от понятия аппроксимации.
источник
В качестве интуитивного подхода рассмотрим, что создание NP-полных задач не всегда так сложно, как в общем случае. Двоичная удовлетворительность (SAT) является NP-полной, но тривиально найти решение A v B v C v D v ... Алгоритмы сложности просто ограничивают наихудший случай, а не средний случай или даже 90% случай ,
Самый простой способ свести проблему NP-complete к чему-то более простому - просто исключить твердые части. Это обман, да. Но часто оставшиеся части все еще полезны для решения реальных проблем. В некоторых случаях грань между «легким» и «трудным» легко провести. Как вы указали для TSP, сложность сильно уменьшается, если вы ограничиваете проблему вокруг «нормальных» направлений, о которых можно подумать. Для других проблем Сложнее найти реальные полезные способы разделения легких и сложных частей.
Чтобы полностью покинуть сферу CS и математики, рассмотрим старую машину. Твой друг хочет водить его. Если вы скажете ему: «Эй, машина работает отлично. Только не превышайте скорость более 95 миль в час. Это отвратительное колебание, которое сбивает вас с дороги», это, вероятно, не имеет большого значения. Твой друг, наверное, все равно хотел взять его с собой по городу. Тем не менее, если вы скажете ему: «Вы должны растянуть сцепление как раз для перехода с 1-го на 2-е, иначе двигатель заглохнет», вашему другу может быть сложнее использовать машину по городу без каких-либо незначительных тренировок.
Аналогично, если проблема с NP-полнотой становится сложной только в экзотических случаях, она довольно быстро уменьшает сложность, когда вы смотрите на субдомены. Однако, если это становится трудным в обычно происходящих случаях, не так много полезных поддоменов, которые избегают сложной части.
источник