Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Полнота/Minesweeper — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| Строка 23: | Строка 23: | ||
== Передача сигнала . == | == Передача сигнала . == | ||
| − | <slides split="-----" width=" | + | <slides split="-----" width="800"> |
[[File:Minesweeper_2022-03-03_08-52-20_image0.png||800px]] | [[File:Minesweeper_2022-03-03_08-52-20_image0.png||800px]] | ||
----- | ----- | ||
[[File:Minesweeper_2022-03-03_08-53-05_image0.png||800px]] | [[File:Minesweeper_2022-03-03_08-53-05_image0.png||800px]] | ||
</slides> | </slides> | ||
| + | |||
| + | |||
| + | == NOR-gate . == | ||
| + | |||
| + | [[File:Minesweeper_2022-03-03_09-00-47_image0.png|center|640px]] | ||
| + | |||
| + | |||
| + | == AND-gate . == | ||
| + | |||
| + | [[File:Minesweeper_2022-03-03_09-04-47_image0.png|center|640px]] | ||
Версия 06:05, 3 марта 2022
- Заголовок
- Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Полнота/Minesweeper
- Автор
- Стас Фомин
- Нижний колонтитул
- Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Полнота/Minesweeper
- Дополнительный нижний колонтитул
- Стас Фомин, 06:38, 3 марта 2022
Содержание
Постановка.
Сапер.
Сапер.
NP? .…
- ?
- Что будет сертификатом?
NP!.
- …
SAT → .
Суперкомпьютер для решения SAT
Передача сигнала .
NOR-gate .
AND-gate .
