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

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 8: Строка 8:
 
{{:3ESAT}}
 
{{:3ESAT}}
  
−
== NP?. ==
+
== NP?… ==
  
−
== Кого сводим к ней?. ==
+
* ?
 +
* Что будет сертификатом?
 +
 
 +
== NP!. ==
 +
Cертификат → вектор, на котором формула истинна.
 +
 
 +
== Кого сводим к ней?.… ==
 +
* 3SAT
 +
* Проблемы:
 +
** Скобки из
 +
*** одного литерала
 +
*** двух литералов
 +
 
 +
== Один литерал в скобке-дизъюнкции. ==
 +
* $\{x_k\}$
 +
* 3-КНФ может быть истинна ←→ $x_k = 1\;\forall k$;
 +
** проверяем, что  $\nexists\:i, j:\:x_i \equiv\bar x_j$
 +
** иначе → сразу невыполнима.
 +
* Подстановка $x_k = 1$
 +
** Выкидываем
 +
*** все дизъюнкции, содержащие литерал $x_k$
 +
*** все литералы $\bar x_i$, выполнимость получившейся КНФ будет равносильна выполнимости исходной.
 +
* Повторяем, пока не избавимся от дизъюнкций из одного литерала.
 +
 
 +
Каждую дизъюнкцию 3-КНФ, содержащую 2 литерала: $\alpha = (x\wedge y)$ заменяем на две: $\beta = (x\wedge y\wedge z)\vee (x\wedge y\wedge\bar z)$. Тогда $\alpha\equiv\beta$.
 +
 
 +
Итого за полиномиальное время получаем КНФ из $3ESAT$, выполнимость которой равносильна выполнимости исходной.

Версия 23:40, 2 марта 2022

S5-ispras-preview.png
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
  • Проблемы:
    • Скобки из
      • одного литерала
      • двух литералов

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

  • $\{x_k\}$
  • 3-КНФ может быть истинна ←→ $x_k = 1\;\forall k$;
    • проверяем, что $\nexists\:i, j:\:x_i \equiv\bar x_j$
    • иначе → сразу невыполнима.
  • Подстановка $x_k = 1$
    • Выкидываем
      • все дизъюнкции, содержащие литерал $x_k$
      • все литералы $\bar x_i$, выполнимость получившейся КНФ будет равносильна выполнимости исходной.
  • Повторяем, пока не избавимся от дизъюнкций из одного литерала.

Каждую дизъюнкцию 3-КНФ, содержащую 2 литерала: $\alpha = (x\wedge y)$ заменяем на две: $\beta = (x\wedge y\wedge z)\vee (x\wedge y\wedge\bar z)$. Тогда $\alpha\equiv\beta$.

Итого за полиномиальное время получаем КНФ из $3ESAT$, выполнимость которой равносильна выполнимости исходной.
  1. ↑ разумеется, три разных литерала! Т.е. нельзя , можно
Источник — «https://discopal.ispras.ru/index.php?title=Полиномиальные_сводимости_и_NP-полные_задачи._Классы_NP,_coNP,_NPC/Полнота/3ESAT&oldid=19919»