Как можно сократить 3-SAT до независимого набора?

Question

Отсюда я читал о твердости NP (стр. 8, 9), и в примечаниях автор сводит задачу в форме 3-SAT к графику, который можно использовать для решения задачи о максимальном независимом множестве.

В этом примере автор преобразует следующую задачу 3-SAT в граф. Проблема 3-SAT:

(a ∨ b ∨ c) ∧ (b ∨ ~c ∨ ~d) ∧ (~a ∨ c ∨ d) ∧ (a ∨ ~b ∨ ~d)

Сгенерированный эквивалентный граф:

Автор утверждает, что два узла соединены ребром, если:

1. Они соответствуют литералам в том же пункте
2. Они соответствуют переменной и ее обратной.

У меня проблемы с пониманием того, как автор придумал эти правила.

• Почему нам нужно рисовать ребра между переменной и ее инверсией?
• Предположим, что есть два предложения, и в пункте 1 есть (a,b,~c), а в пункте 2 есть (~a,b,c), чтобы соединить пункт 1 с пунктом 2, почему мы должны соединять a и ~a? Почему мы не можем связать (пункт 1) с c (пункт 2) вместо этого?

Answer 1

Я думаю, что можно прояснить проблему - это концепция сокращения. Предположим, вы знакомы с проблемой, скажем, X(то есть 3-SAT)[ что это значит знакомо? Вы знаете, сколько трудно решить X ]. Также вы в настоящее время работаете над анализом еще одной новой проблемы, скажем, Y(т.е. независимый набор)...

Как знание о X может помочь вам найти Y? Если вы можете найти связь (то есть сокращение) между ними, то вы можете использовать знания о X к Y. Что-то вроде "Y сложнее, чем X" или "Y так же сложно, как X". Так что это решение хочет сделать, это найти связь между двумя проблемами.

В теории вычислимости и теории вычислительной сложности редукция - это алгоритм преобразования одной задачи в другую. Сокращение от одной проблемы к другой может использоваться, чтобы показать, что вторая проблема, по меньшей мере, столь же сложна, как и первая.

Два правила, которые вы здесь отметили, - все это (то есть отношение).

1. Вы не можете выбрать две вершины ребра одновременно. Также вы не можете установить переменную и ее отрицание TRUE одновременно.
2. Вы должны иметь переменную TRUE в предложении. Также, чтобы максимизировать количество выбранных вершин, вы должны выбрать один узел из каждого предложения.

Это показывает, откуда берутся эти правила.

PS: То, что здесь отмечено, не является точным доказательством решения проблемы 3-SAT для независимого набора. Это объяснение только для того, чтобы вы лучше поняли, какую процедуру хотят выполнить доказательства. Доказательство оставлено академическим заметкам.

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

Также есть некоторые обозначения, чтобы показать, что X < Y с другим порядком времени в качестве индекса <, Более того, если вы покажете, что X < Y а также Y < X, Это означает, что эти проблемы имеют равную твердость.

В заключение отметим, что то, что цитируется в примечании, говорит о сокращении ... сокращение - это алгоритм....