Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Полнота/3ESAT — различия между версиями

Текущая версия на 06:38, 3 марта 2022

Slide Show

Заголовок: Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Полнота/3ESAT
Автор: Стас Фомин
Нижний колонтитул: Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Полнота/3ESAT
Дополнительный нижний колонтитул: Стас Фомин, 06:38, 3 марта 2022

Постановка.

3SAT.

3SAT или «3-Выполнимость» — частный случай задачи SAT, в которой все дизъюнкции имеют не более чем три терма.

Однако, показано, что несмотря на это ограничение, 3SAT является NP-полной задачей.

3ESAT.

Частный случай 3SAT, когда в каждой скобке ровно три литерала^[1].

NP?.…

?
Что будет сертификатом?

NP!.

Cертификат → вектор, на котором формула истинна.

Кого сводим к ней?.…

3SAT
Проблемы:
- Скобки из
  - одного литерала
  - двух литералов

Один литерал в скобке-дизъюнкции. …

3-КНФ может быть истинна ←→ ;
- проверяем, что
- иначе → сразу невыполнима.
Подстановка
- Выкидываем
  - все дизъюнкции, содержащие литерал
  - все литералы ,
  - выполнимость получившейся КНФ равносильна выполнимости исходной
Повторяем, пока не избавимся от дизъюнкций из одного литерала.

Два литерала в скобке-дизъюнкции. …

дизъюнкцию 3-КНФ заменяем на две:
- .
→ .

↑ разумеется, три разных литерала! Т.е. нельзя

, можно

[1]

@@ Строка 1: / Строка 1: @@
-<slideshow headingmark="." incmark="…" scaled=1 style="ispras">
+<noinclude><slideshow incmark="…" headingmark="." scaled=1 style="ispras"/></noinclude>
-;author: Stas Fomin
-</slideshow>
-== Постановка ==
+== Постановка. ==
+=== 3SAT. ===
+{{:3SAT}}
+=== 3ESAT. ===
 {{:3ESAT}}
-== NP? ==
+== NP?.… ==
+* ?
+* Что будет сертификатом?
+== NP!. ==
+Cертификат → вектор, на котором формула истинна.
+== Кого сводим к ней?.… ==
+* 3SAT
+* Проблемы:
+** Скобки из
+*** одного литерала
+*** двух литералов
+== Один литерал в скобке-дизъюнкции. … ==
+* <m>\{x_k\}</m>
+* 3-КНФ может быть истинна ←→ <m>x_k = 1\;\forall k</m>;
+** проверяем, что  <m>\nexists\:i, j:\:x_i \equiv\bar x_j</m>
+** иначе → сразу невыполнима.
+* Подстановка <m>x_k = 1</m>
+** Выкидываем
+*** все дизъюнкции, содержащие литерал <m>x_k</m>
+*** все литералы <m>\bar x_i</m>,
+*** выполнимость получившейся КНФ равносильна выполнимости исходной
+* Повторяем, пока не избавимся от дизъюнкций из одного литерала.
-== Кого сводим к ней? ==
+== Два литерала в скобке-дизъюнкции. … ==
+* дизъюнкцию 3-КНФ <m>$\alpha = (x\wedge y)</m> заменяем на две:
+** <m>\beta = (x\wedge y\wedge z)\vee (x\wedge y\wedge\bar z)</m>.
+* → <m>\alpha\equiv\beta</m>.