В теории вычислимости и сложности (и, возможно, в других областях) сокращения являются повсеместными. Существует много видов, но принцип остается тем же: показать, что одна проблема , по крайней мере, так же трудна, как и другая проблема путем сопоставления экземпляров из с эквивалентными по решению в . По сути, мы показываем, что любой решатель для может также решить если мы позволим ему использовать функцию редукции в качестве препроцессора.
Я выполнил свою долю сокращений за эти годы, и что-то продолжает беспокоить меня. В то время как каждое новое сокращение требует (более или менее) творческого построения, задача может быть повторяющейся. Есть ли пул канонических методов?
Какие приемы, шаблоны и приемы можно регулярно использовать для построения функций сокращения?
Это должно стать справочным вопросом . Поэтому, пожалуйста, позаботьтесь о том, чтобы дать общие, дидактически представленные ответы, которые иллюстрируются хотя бы одним примером, но, тем не менее, охватывают многие ситуации. Благодарность!
Ответы:
Особый случай
Предположим , мы хотим показать относительно некоторого понятия редукции R . Если L 1 представляет собой частный случай из L 2 , что вполне тривиально: мы можем существенно использовать тождественную функцию. Интуиция за этим ясна: общий случай, по крайней мере, такой же сложный, как и особый случай.L1≤RL2 R L1 L2
В «практике» нам дают и мы сталкиваемся с проблемой выбора хорошего партнера по восстановлению L 1 , то есть находим особый случай L 2 , который оказался R- трудным.L2 L1 L2 R
Простой пример
Предположим, мы хотим показать, что KNAPSACK NP- сложен . К счастью, мы знаем, что SUBSET-SUM является NP-полной, и это действительно особый случай KNAPSACK. Снижение
хватает; - это экземпляр KNAPSACK, который спрашивает, можем ли мы достичь хотя бы значения v со значениями элементов в V, чтобы соответствующие веса из W оставались ниже w в целом. Нам не нужны ограничения по весу для симуляции SUBSET-SUM, поэтому мы просто устанавливаем для них тавтологические значения.( V, Вт, v , w ) v В W вес
Простая задача упражнений
Рассмотрим задачу MAX-3SAT: учитывая пропозициональную формулу и целое число k , решите, существует ли интерпретация φ, которая удовлетворяет хотя бы k пунктам. Покажите, что это NP-хард.φ К φ К
пример
Предположим, что мы исследуем проблему SUBSET-SUM и хотим показать, что она NP-трудная.
Нам повезло, и мы знаем, что проблема PARTITION является NP-полной. Мы подтверждаем, что это действительно частный случай SUBSET-SUM и формулируем
где - входной набор PARTITION, а ( A , k ) - экземпляр для SUBSET-SUM, который запрашивает после подмножества A суммирования к k . Здесь мы должны позаботиться о том, чтобы не было подходящего k ; в этом случае мы даем произвольный невозможный случай.A ( А , К ) A К К
Упражнение Проблема
Рассмотрим задачу LONGEST-PATH: учитывая направленный граф , узлы s , t из G и целое число k , решите, существует ли простой путь из s в t в G длиной не менее k .г с , т г К s T г К
Покажите, что самый длинный путь - NP-сложный.
источник
Использование известной проблемы поблизости
Когда сталкиваешься с проблемой, которая кажется сложной, часто стоит попытаться найти похожую проблему, которая уже доказала свою трудность. Или, возможно, вы сразу можете увидеть, что проблема очень похожа на известную проблему.
Пример задачи
Рассмотреть проблему
мы хотим показать это -полный. Мы быстро заметим, что это очень близко к проблеме, которую мы уже знаем, это сложная проблема , а именно проблема выполнимости (SAT) .NP
Членство в легко показать. Сертификат двух назначений. Очевидно, что за полиномиальное время можно проверить, удовлетворяют ли присвоения формуле.NP
-твердость следует из сокращения с SAT . Учитывая формулу φ , мы модифицируем ее, вводя новую переменную v . Мы добавляем новый пункт ( v ∨ ¬ v ) в формулу. Теперь, если φNP SAT φ v ( V ∨ ¬ v ) φ выполнимо, оно будет выполнимо как при и при v = ⊤ . Следовательно, φ имеет по крайней мере 2 удовлетворяющих назначения. С другой стороны, если φ не выполнимо, оно определенно не станет выполнимым независимо от значения v .v = ⊥ v = ⊤ φ φ v
Отсюда следует, что является N P -полным, что мы и хотели показать.DOUBLE-СБ Н П
Нахождение проблем поблизости
Уменьшение проблем - это своего рода искусство, и опыт и изобретательность часто необходимы. К счастью, многие сложные проблемы уже известны . Garey and Johnson's Computers and Intractability: руководство по теории NP-полноты является классическим, в его приложении перечислены многие проблемы. Google Scholar тоже друг.
источник
В области вычислимости мы часто исследуем наборы машин Тьюринга. То есть наши объекты являются функциями, и мы имеем доступ к нумерации Гёделя . Это замечательно, потому что мы можем делать в значительной степени то, что мы хотим, с помощью функции ввода, пока мы остаемся вычислимыми.
Предположим, мы хотим показать, что не разрешима. Наша цель - достичь эквивалентности Doom.L
с проблемой остановки (или любые другие неразрешимыми языком / проблем).K={⟨M⟩∣M(⟨M⟩) halts}
Таким образом, нам нужно придумать отображение computable¹⟨M⟩↦⟨fM⟩ так , что всегда вычислят. Это творческий акт, основанный на эквивалентности гибели. Посмотрите несколько примеров, чтобы понять, как это работает:fM
То же самое работает для демонстрации того, что не является полуразрешимым, выбирая неполучаемые языки в качестве партнера по сокращению, напримерL :K¯¯¯¯¯
источник
это зависит от участвующих классов сложности, и от того, хочет ли кто-то перейти от данного к неизвестному B или от неизвестного B к данному AA B B A . общий сценарий - доказать проблемы NP Hard или NP Complete. распространенная техника состоит в создании «гаджетов» в одном домене, которые ведут себя определенным образом, имитируя поведение другого домена. например, чтобы преобразовать SAT в покрытие вершин, в оболочке вершин создаются «гаджеты», которые ведут себя аналогично предложениям SAT, например, в следующем слайд-шоу: NP Полное сокращение по Кришнамурти (также с примером для пути Гамильтона).
полезной стратегией является работа с большими подборками задач из рассматриваемого класса сложности и поиск «очевидных ближайших проблем» к исследуемой проблеме. отличным справочником по этим направлениям является « Компьютеры и непрактичность», руководство по теории полноты NP, Гэри и Джонсон, организованные по различным типам задач.
источник