Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Полнота/Minesweeper — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) м (StasFomin переименовал страницу Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Полнота/Minesweep в [[Полиномиальные сводимости и NP-…) |
StasFomin (обсуждение | вклад) |
||
| Строка 4: | Строка 4: | ||
=== Сапер. === | === Сапер. === | ||
[[File:Minesweep_2022-03-03_08-43-21_image0.png|center|800px]] | [[File:Minesweep_2022-03-03_08-43-21_image0.png|center|800px]] | ||
| + | |||
| + | === Сапер. === | ||
| + | [[File:Minesweeper_2022-03-03_08-49-32_image0.png|center|800px]] | ||
== NP? .… == | == NP? .… == | ||
| Строка 11: | Строка 14: | ||
== NP!. == | == NP!. == | ||
* … | * … | ||
| + | |||
| + | === SAT → . === | ||
| + | |||
| + | [[File:Minesweeper_2022-03-03_08-50-39_image0.png|center|800px]] | ||
| + | |||
| + | == Суперкомпьютер для решения SAT == | ||
| + | |||
| + | |||
| + | == Передача сигнала . == | ||
| + | <slides split="-----" width="600"> | ||
| + | [[File:Minesweeper_2022-03-03_08-52-20_image0.png||800px]] | ||
| + | ----- | ||
| + | [[File:Minesweeper_2022-03-03_08-53-05_image0.png||800px]] | ||
| + | </slides> | ||
Версия 05:55, 3 марта 2022
- Заголовок
- Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Полнота/Minesweeper
- Автор
- Стас Фомин
- Нижний колонтитул
- Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Полнота/Minesweeper
- Дополнительный нижний колонтитул
- Стас Фомин, 06:38, 3 марта 2022
Содержание
Постановка.
Сапер.
Сапер.
NP? .…
- ?
- Что будет сертификатом?
NP!.
- …
SAT → .
Суперкомпьютер для решения SAT
Передача сигнала .
