Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Полнота/3ESAT — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | <slideshow incmark="…" scaled=1 style="ispras"/> | + | <slideshow incmark="…" headingmark="." scaled=1 style="ispras"/> |
| − | == Постановка == | + | == Постановка. == |
| − | === 3SAT === | + | === 3SAT. === |
{{:3SAT}} | {{:3SAT}} | ||
| − | === 3ESAT === | + | === 3ESAT. === |
{{:3ESAT}} | {{:3ESAT}} | ||
| − | == NP? == | + | == NP?. == |
| − | == Кого сводим к ней? == | + | == Кого сводим к ней?. == |
Версия 23:13, 2 марта 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?.
Кого сводим к ней?.
- ↑ разумеется, три разных литерала! Т.е. нельзя , можно