Как построить сокращения между проблемами, чтобы доказать, что проблема является NP-полной?

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

Там нет волшебной пули; Доказательства NP-твердости трудны. Однако для всех таких доказательств существует общая основа. Многие студенты, которые борются с NP-доказательствами твердости, не понимают, что они должны делать, что, очевидно, делает невозможным выяснить, как это сделать. Итак, вот что нужно сделать, чтобы доказать проблему NP-Hard.

Во-первых, если вы просто не делаете домашнее задание, вы должны решить, какую сложную задачу решить, чтобы решить вашу проблему . Это в значительной степени вопрос о «запахе». Если число 3 появляется в либо месте в проблемы, попробуйте уменьшить значение из или или . (Да, я серьезно.) Если ваша проблема заключается в поиске оптимальной подпоследовательности, перестановки или пути, попробуйте уменьшить значение из или . Если ваша проблема требует наименьшего подмножества с определенным свойством, попробуйте ; если он запрашивает наибольшее подмножество с определенным свойством, попробуйте3 С о л о г 3 Р т т я т я о п Н м я л т о н я п С у с л е Н м я л т о н я п р т h C l i q u e I n d $\mathsf{3SAT}$$\mathsf{3Color}$$\mathsf{3Partition}$$\mathsf{HamiltonianCycle}$$\mathsf{HamiltonianPath}$$\mathsf{Clique}$$\mathsf{IndependentSet}$, Если ваша проблема заключается в выполнении чего-либо в самолете, попробуйте или . И так далее. Если ваша проблема не «пахнет» чем-то, то или , вероятно, является лучшим выбором.Р л а н с т Т С Р 3 С Т С я г с ц я т S A $\mathsf{PlanarCircuitSAT}$$\mathsf{PlanarTSP}$$\mathsf{3SAT}$$\mathsf{CircuitSAT}$

Очевидно, что вам уже нужно точно знать, как все эти проблемы определены , и чем проще проблема, которую вы решаете, тем лучше. Поэтому, как бы ни был хорош результат в конце, я не рекомендую уменьшать из или или или .$\mathsf{Minesweeper}$$\mathsf{Tetris}$$\mathsf{OneCheckersMove}$$\mathsf{SuperMarioBros}$

Во-вторых, фактическое сокращение. Чтобы свести проблему X (которую вы знаете, NP-сложная) к проблеме Y (которую вы пытаетесь доказать, NP-сложная, вам нужно описать алгоритм, который преобразует произвольный экземпляр X в допустимый экземпляр Y Алгоритм редукции должен делать что-то конкретное с каждой «особенностью» X-экземпляра, часть вывода для каждой «функции» обычно называется гаджетом .

Но в чем особенность? Это зависит от проблемы X. Например:

• Чтобы преобразовать экземпляр , вам понадобится гаджет для каждой переменной и для каждого предложения в формуле ввода. Каждый переменный гаджет должен иметь два «состояния», которые соответствуют «истине» и «ложи». Каждый гаджет предложения также должен иметь несколько «состояний», каждое из которых каким-то образом заставляет хотя бы один из литералов в этом предложении быть истинными. (Состояния не являются частью вывода алгоритма редукции.)$\mathsf{3SAT}$

• Чтобы преобразовать экземпляр , вам потребуется гаджет для каждой вершины и каждого ребра входного графа, а также другой гаджет для определения трех цветов.$\mathsf{3Color}$

• Чтобы преобразовать экземпляр , вам потребуется гаджет для каждого входа, для каждого провода и для каждого затвора во входной цепи.$\mathsf{PlanarCircuitSat}$

Конкретный вид гаджет зависит от задачи Y, тот , который вы восстанавливающие к . Например, если вы сводите проблему к графикам, ваши гаджеты будут небольшими подграфами; см. статью в Википедии. Если вы сводите проблему к планированию, каждый гаджет будет набором заданий, которые нужно запланировать. Если вы сводитесь к проблеме с Марио , то каждый гаджет будет представлять собой набор блоков, кирпичей и Koopas.

Это может сбить с толку, если обе проблемы связаны с одним и тем же типом объекта. Например, если X и Y являются проблемами с графами, ваш алгоритм преобразует один граф (экземпляр X) в другой граф (экземпляр Y). Мудро выбирайте обозначения, чтобы не перепутать эти два графика. Я также настоятельно рекомендую использовать несколько цветов чернил.

Наконец, ваш алгоритм сокращения должен удовлетворять трем свойствам:

• Работает за полиномиальное время. (Это обычно легко.)

• Если вашему алгоритму сокращения дается положительный экземпляр X в качестве входных данных, он создает положительный экземпляр Y в качестве выходных данных.

• Если ваш алгоритм редукции выдает положительный экземпляр Y в качестве вывода, ему должно быть дан положительный экземпляр X в качестве ввода.

Здесь есть важная тонкость. Ваш алгоритм сокращения работает только в одном направлении, от экземпляров X до экземпляров Y, но для доказательства правильности алгоритма требуется рассуждение о преобразовании в обоих направлениях. Вы также должны помнить, что ваш алгоритм редукции не может определить, является ли данный экземпляр X положительным или отрицательным, что потребовало бы решения сложной задачи NP за полиномиальное время!

Вот что . Как только приходит с практикой.

Джефф обрисовывает в общих чертах наиболее распространенную стратегию: знай множество задач, завершенных NP, найди одну, которая подходит и сделай легкое сокращение.

Другая правильная стратегия - всегда использовать 3SAT (или любую другую проблему). Это может сделать некоторые сокращения более сложными, но положительным моментом является то, что у вас есть большой опыт выражения сатинируемости в других типах проблем. Таким образом, вы экономите время на поиске хорошего партнера по сокращению (включая тупики) и надеетесь, что ваш опыт позволит вам быстро выполнить сокращение, даже если оно сложнее.

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