Каковы общие методы уменьшения проблем друг с другом?

40

В теории вычислимости и сложности (и, возможно, в других областях) сокращения являются повсеместными. Существует много видов, но принцип остается тем же: показать, что одна проблема L1 , по крайней мере, так же трудна, как и другая проблема L2 путем сопоставления экземпляров из с эквивалентными по решению в . По сути, мы показываем, что любой решатель для может также решить если мы позволим ему использовать функцию редукции в качестве препроцессора.L2L1L1L2

Я выполнил свою долю сокращений за эти годы, и что-то продолжает беспокоить меня. В то время как каждое новое сокращение требует (более или менее) творческого построения, задача может быть повторяющейся. Есть ли пул канонических методов?

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

Это должно стать справочным вопросом . Поэтому, пожалуйста, позаботьтесь о том, чтобы дать общие, дидактически представленные ответы, которые иллюстрируются хотя бы одним примером, но, тем не менее, охватывают многие ситуации. Благодарность!

Рафаэль
источник
Смотрите здесь для некоторых мыслей о поиске подходящих партнеров и идей для сокращения.
Рафаэль

Ответы:

18

Особый случай

Предположим , мы хотим показать относительно некоторого понятия редукции R . Если L 1 представляет собой частный случай из L 2 , что вполне тривиально: мы можем существенно использовать тождественную функцию. Интуиция за этим ясна: общий случай, по крайней мере, такой же сложный, как и особый случай.L1RL2RL1L2

В «практике» нам дают и мы сталкиваемся с проблемой выбора хорошего партнера по восстановлению L 1 , то есть находим особый случай L 2 , который оказался R- трудным.L2L1L2р

Простой пример

Предположим, мы хотим показать, что KNAPSACK NP- сложен . К счастью, мы знаем, что SUBSET-SUM является NP-полной, и это действительно особый случай KNAPSACK. Снижение

е(A,К)знак равно(A,(1,...,1),К,|A|)

хватает; - это экземпляр KNAPSACK, который спрашивает, можем ли мы достичь хотя бы значения v со значениями элементов в V, чтобы соответствующие веса из W оставались ниже w в целом. Нам не нужны ограничения по весу для симуляции SUBSET-SUM, поэтому мы просто устанавливаем для них тавтологические значения.(В,W,v,вес)vВWвес

Простая задача упражнений

Рассмотрим задачу MAX-3SAT: учитывая пропозициональную формулу и целое число k , решите, существует ли интерпретация φ, которая удовлетворяет хотя бы k пунктам. Покажите, что это NP-хард.φКφК

3SAT - это особый случай; с m достаточно числа предложений в φ .е(φ)знак равно(φ,м)мφ

пример

Предположим, что мы исследуем проблему SUBSET-SUM и хотим показать, что она NP-трудная.

Нам повезло, и мы знаем, что проблема PARTITION является NP-полной. Мы подтверждаем, что это действительно частный случай SUBSET-SUM и формулируем

f(A)={(A,12ΣaAa),ΣaAaмодификация2знак равно0(A,1+ΣaA|a|),еще

где - входной набор PARTITION, а ( A , k ) - экземпляр для SUBSET-SUM, который запрашивает после подмножества A суммирования к k . Здесь мы должны позаботиться о том, чтобы не было подходящего k ; в этом случае мы даем произвольный невозможный случай.A(A,К)AКК

Упражнение Проблема

Рассмотрим задачу LONGEST-PATH: учитывая направленный граф , узлы s , t из G и целое число k , решите, существует ли простой путь из s в t в G длиной не менее k .гs,TгКsTгК

Покажите, что самый длинный путь - NP-сложный.

HAMILTON-CYCLE является хорошо известной NP-полной проблемой и частным случаем LONGEST-PATH; для произвольного узла v в G достаточно. Обратите внимание, в частности, как сокращение от HAMILTON-PATH требует больше работы.е(г)знак равно(г,v,v,N)vг

Рафаэль
источник
2
Вот пример, названный проблемой путешествующего покупателя (TPP), который имеет много трудных проблем в качестве своего особого случая.
Юхо
Другим примером вычислимости является специальная проблема остановки (которая обычно прямо доказывается неразрешимой), частный случай общей проблемы остановки.
Рафаэль
Действительно ли KNAPSACK - правильное сокращение от SUBSET-SUM? KNAPSACK запрашивает значение а SUBSET-SUM запрашивает точное значение, нет? Например, экземпляр SUBSET-SUM {> =v будет «no' инстанции (я не могу получить именно 4 из только один элемент со значением 5), но ваше сокращение ранце уменьшило бычто{ 5 } , { 1 } , 4 , 1 и 5 > 4 , такэто будет «yes' инстанции там ... Или я чтото отсутствует? {5},4{5},{1},4,15>4
Джонни
15

Использование известной проблемы поблизости

Когда сталкиваешься с проблемой, которая кажется сложной, часто стоит попытаться найти похожую проблему, которая уже доказала свою трудность. Или, возможно, вы сразу можете увидеть, что проблема очень похожа на известную проблему.

Пример задачи

Рассмотреть проблему

DOUBLE-SAT={φφ is a boolean formula with at least 2 satisfying assignments }

мы хотим показать это -полный. Мы быстро заметим, что это очень близко к проблеме, которую мы уже знаем, это сложная проблема , а именно проблема выполнимости (SAT) .NP

Членство в легко показать. Сертификат двух назначений. Очевидно, что за полиномиальное время можно проверить, удовлетворяют ли присвоения формуле.NP

-твердость следует из сокращения с SAT . Учитывая формулу φ , мы модифицируем ее, вводя новую переменную v . Мы добавляем новый пункт ( v ¬ v ) в формулу. Теперь, если φNPSATφv(v¬v)φ выполнимо, оно будет выполнимо как при и при v = . Следовательно, φ имеет по крайней мере 2 удовлетворяющих назначения. С другой стороны, если φ не выполнимо, оно определенно не станет выполнимым независимо от значения v .v= ⊥vзнак равноφφv

Отсюда следует, что является N P -полным, что мы и хотели показать.DOUBLE-СБNп

Нахождение проблем поблизости

Уменьшение проблем - это своего рода искусство, и опыт и изобретательность часто необходимы. К счастью, многие сложные проблемы уже известны . Garey and Johnson's Computers and Intractability: руководство по теории NP-полноты является классическим, в его приложении перечислены многие проблемы. Google Scholar тоже друг.

Юхо
источник
6

В области вычислимости мы часто исследуем наборы машин Тьюринга. То есть наши объекты являются функциями, и мы имеем доступ к нумерации Гёделя . Это замечательно, потому что мы можем делать в значительной степени то, что мы хотим, с помощью функции ввода, пока мы остаемся вычислимыми.

Предположим, мы хотим показать, что не разрешима. Наша цель - достичь эквивалентности Doom.L

MKfML

с проблемой остановки (или любые другие неразрешимыми языком / проблем).K={MM(M) halts}

Таким образом, нам нужно придумать отображение computable¹ MfM так , что всегда вычислят. Это творческий акт, основанный на эквивалентности гибели. Посмотрите несколько примеров, чтобы понять, как это работает:fM

То же самое работает для демонстрации того, что не является полуразрешимым, выбирая неполучаемые языки в качестве партнера по сокращению, напримерL :K¯


  1. Здесь начинается нумерация Гёделя: мы получаем вычислимость этого отображения (обычно) бесплатно.
Рафаэль
источник
-2

это зависит от участвующих классов сложности, и от того, хочет ли кто-то перейти от данного к неизвестному B или от неизвестного B к данному AABBA . общий сценарий - доказать проблемы NP Hard или NP Complete. распространенная техника состоит в создании «гаджетов» в одном домене, которые ведут себя определенным образом, имитируя поведение другого домена. например, чтобы преобразовать SAT в покрытие вершин, в оболочке вершин создаются «гаджеты», которые ведут себя аналогично предложениям SAT, например, в следующем слайд-шоу: NP Полное сокращение по Кришнамурти (также с примером для пути Гамильтона).

полезной стратегией является работа с большими подборками задач из рассматриваемого класса сложности и поиск «очевидных ближайших проблем» к исследуемой проблеме. отличным справочником по этим направлениям является « Компьютеры и непрактичность», руководство по теории полноты NP, Гэри и Джонсон, организованные по различным типам задач.

ВЗН
источник
2
Интересно, заметили ли вы сноску в вопросе? Я думаю, что ответы должны быть более конкретными и демонстрировать, как применяется конкретный метод. Это кажется довольно расплывчатым и общим. Как улучшение, как вы показываете, как гаджеты могут быть построены и использованы?
Юхо
2
ABBA
PowerPoint показывает два примера использования гаджетов. пример ближайшей проблемы: предположим, у кого-то есть проблема, связанная с теорией чисел. есть раздел G & J, связанный с теорией чисел. и так далее. Что касается других классов сложности за пределами NP, их много, но списки проблем не так полны или не легко получены. другими словами, чтобы сузить исходный вопрос, может быть, его следует ограничить полным сокращением NP ...?
vzn
2
Я рекомендую добавить всю информацию в ответ, так как комментарии могут быть удалены в любое время. Ссылка на слайды может прерваться и завтра. К чему я стремился с соседней проблемой: что мне делать , когда я нахожу проблему, которая выглядит похожей (предположим, я абсолютный новичок)?
Юхо