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

Материал из DISCOPAL
Перейти к: навигация, поиск
S5-ispras-preview.png
Slide Show
Заголовок

Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Полнота/3ESAT
Автор
Stas Fomin
Нижний колонтитул
Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Полнота/3ESAT
Дополнительный нижний колонтитул

Stas Fomin, 06:38, 3 марта 2022

Постановка

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

NP?

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

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

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.

Источник — «https://discopal.ispras.ru/index.php?title=Полиномиальные_сводимости_и_NP-полные_задачи._Классы_NP,_coNP,_NPC/Полнота/3ESAT&oldid=19914»