Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Полнота/Minesweeper
Стас Фомин
Постановка
Сапер
Сапер
NP?
?
Что будет сертификатом?
NP!
…
SAT →
Передача сигнала
NOR-gate
AND-gate
OR-gate
Из NOT & AND
Деморгана
За полином по SAT-формуле строим САПЕРА