Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Полнота/3ESAT — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «<slideshow headingmark="." incmark="…" scaled=1 style="ispras"> ;author: Stas Fomin </slideshow> == Постановка == {{3ESAT}} == NP? == == Кого…») |
StasFomin (обсуждение | вклад) |
||
| Строка 4: | Строка 4: | ||
== Постановка == | == Постановка == | ||
| − | {{3ESAT}} | + | {{:3ESAT}} |
== NP? == | == NP? == | ||
== Кого сводим к ней? == | == Кого сводим к ней? == | ||
Версия 23:00, 2 марта 2022
- Заголовок
- Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Полнота/3ESAT
- Автор
- Stas Fomin
- Нижний колонтитул
- Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Полнота/3ESAT
- Дополнительный нижний колонтитул
- Stas Fomin, 06:38, 3 марта 2022
Постановка
Частный случай 3SAT, когда в каждой скобке ровно три литерала[1].
NP?
Кого сводим к ней?
- ↑ разумеется, три разных литерала! Т.е. нельзя , можно