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

Материал из DISCOPAL
Перейти к: навигация, поиск
S5-ispras-preview.png
Slide Show
Заголовок

Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Полнота/Minesweeper
Автор
Стас Фомин
Нижний колонтитул
Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Полнота/Minesweeper
Дополнительный нижний колонтитул

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

Постановка.

Сапер.

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

Суперкомпьютер для решения SAT

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

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-формуле строим САПЕРА .

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.

Источник — «https://discopal.ispras.ru/index.php?title=Полиномиальные_сводимости_и_NP-полные_задачи._Классы_NP,_coNP,_NPC/Полнота/Minesweeper&oldid=19959»