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

Стас Фомин, 06:38, 3 марта 2022

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

Стас Фомин

Постановка

Сапер

Minesweep 2022-03-03 08-43-21 image0.png

Сапер

Minesweeper 2022-03-03 08-49-32 image0.png

NP?

  •  ?
  • Что будет сертификатом?

NP!

  • …

SAT →

Minesweeper 2022-03-03 08-50-39 image0.png

Передача сигнала

Minesweeper 2022-03-03 08-52-20 image0.png

Minesweeper 2022-03-03 08-53-05 image0.png

NOR-gate

Minesweeper 2022-03-03 09-00-47 image0.png

AND-gate

Minesweeper 2022-03-03 09-04-47 image0.png
Minesweeper 2022-03-03 09-09-17 image0.png
Minesweeper 2022-03-03 09-10-42 image0.png
Minesweeper 2022-03-03 09-11-57 image0.png

OR-gate

  • Из NOT & AND
  • Деморгана

За полином по SAT-формуле строим САПЕРА