Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Полнота/Minesweeper — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
Строка 1: | Строка 1: | ||
− | <slideshow incmark="…" headingmark="." scaled=1 style="ispras"/> | + | <noinclude><slideshow incmark="…" headingmark="." scaled=1 style="ispras"/></noinclude> |
== Постановка. == | == Постановка. == |
Текущая версия на 06:38, 3 марта 2022
- Заголовок
- Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Полнота/Minesweeper
- Автор
- Стас Фомин
- Нижний колонтитул
- Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Полнота/Minesweeper
- Дополнительный нижний колонтитул
- Стас Фомин, 06:38, 3 марта 2022
Содержание
Постановка.
Сапер.
Сапер.
NP? .…
- ?
- Что будет сертификатом?
NP!.
- …
SAT → .
Суперкомпьютер для решения SAT
Передача сигнала .
NOR-gate .
AND-gate .
OR-gate .
- Из NOT & AND
- Деморгана