Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Полнота/Minesweeper — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) м (StasFomin переименовал страницу Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Полнота/Minesweep в [[Полиномиальные сводимости и NP-…) |
StasFomin (обсуждение | вклад) |
||
(не показаны 3 промежуточные версии этого же участника) | |||
Строка 1: | Строка 1: | ||
− | <slideshow incmark="…" headingmark="." scaled=1 style="ispras"/> | + | <noinclude><slideshow incmark="…" headingmark="." scaled=1 style="ispras"/></noinclude> |
== Постановка. == | == Постановка. == | ||
=== Сапер. === | === Сапер. === | ||
[[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="800"> | ||
+ | [[File:Minesweeper_2022-03-03_08-52-20_image0.png||800px]] | ||
+ | ----- | ||
+ | [[File:Minesweeper_2022-03-03_08-53-05_image0.png||800px]] | ||
+ | </slides> | ||
+ | |||
+ | |||
+ | == NOR-gate . == | ||
+ | |||
+ | [[File:Minesweeper_2022-03-03_09-00-47_image0.png|center|640px]] | ||
+ | |||
+ | |||
+ | == AND-gate . == | ||
+ | |||
+ | <slides split="-----" width="800"> | ||
+ | [[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:38, 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
- Деморгана