Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Полнота/3ESAT — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| (не показано 6 промежуточных версий этого же участника) | |||
| Строка 1: | Строка 1: | ||
| − | <slideshow incmark="…" headingmark="." scaled=1 style="ispras"/> | + | <noinclude><slideshow incmark="…" headingmark="." scaled=1 style="ispras"/></noinclude> |
== Постановка. == | == Постановка. == | ||
| Строка 8: | Строка 8: | ||
{{:3ESAT}} | {{:3ESAT}} | ||
| − | == NP?… == | + | == NP?.… == |
* ? | * ? | ||
| Строка 23: | Строка 23: | ||
*** двух литералов | *** двух литералов | ||
| − | == Один литерал в скобке-дизъюнкции. == | + | == Один литерал в скобке-дизъюнкции. … == |
* <m>\{x_k\}</m> | * <m>\{x_k\}</m> | ||
* 3-КНФ может быть истинна ←→ <m>x_k = 1\;\forall k</m>; | * 3-КНФ может быть истинна ←→ <m>x_k = 1\;\forall k</m>; | ||
| Строка 35: | Строка 35: | ||
* Повторяем, пока не избавимся от дизъюнкций из одного литерала. | * Повторяем, пока не избавимся от дизъюнкций из одного литерала. | ||
| − | + | == Два литерала в скобке-дизъюнкции. … == | |
| − | + | * дизъюнкцию 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>. | ||
Текущая версия на 06:38, 3 марта 2022
- Заголовок
- Полиномиальные сводимости и 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-КНФ заменяем на две:
- .
- → .