Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Полнота/Minesweeper — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| Строка 37: | Строка 37: | ||
== AND-gate . == | == AND-gate . == | ||
| + | <slides split="-----" width="800"> | ||
[[File:Minesweeper_2022-03-03_09-04-47_image0.png|center|640px]] | [[File:Minesweeper_2022-03-03_09-04-47_image0.png|center|640px]] | ||
| + | ----- | ||
| + | [[File:Minesweeper_2022-03-03_09-09-17_image0.png|center|640px]] | ||
| + | ----- | ||
| + | [[File:Minesweeper_2022-03-03_09-10-42_image0.png|center|640px]] | ||
| + | ----- | ||
| + | [[File:Minesweeper_2022-03-03_09-11-57_image0.png|center|640px]] | ||
| + | </slides> | ||
| + | |||
| + | === OR-gate . === | ||
| + | * Из NOT & AND | ||
| + | * Деморгана | ||
| + | |||
| + | === За полином по SAT-формуле строим САПЕРА . === | ||
Версия 06:14, 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
- Деморгана