Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Полнота/3ESAT
Материал из DISCOPAL
< Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC | Полнота
Версия от 23:01, 2 марта 2022; StasFomin (обсуждение | вклад)
- Заголовок
- Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Полнота/3ESAT
- Автор
- Стас Фомин
- Нижний колонтитул
- Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Полнота/3ESAT
- Дополнительный нижний колонтитул
- Стас Фомин, 06:38, 3 марта 2022
Содержание
Постановка
3SAT
3SAT или «3-Выполнимость» — частный случай задачи SAT, в которой все дизъюнкции имеют не более чем три терма.
Однако, показано, что несмотря на это ограничение, 3SAT является NP-полной задачей.
3ESAT
Частный случай 3SAT, когда в каждой скобке ровно три литерала[1].
NP?
Кого сводим к ней?
- ↑ разумеется, три разных литерала! Т.е. нельзя , можно
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.