Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Полнота/Vertex-3-Coloring — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| (не показано 6 промежуточных версий этого же участника) | |||
| Строка 1: | Строка 1: | ||
| − | <slideshow incmark="…" headingmark="." scaled=1 style="ispras"/> | + | <noinclude><slideshow incmark="…" headingmark="." scaled=1 style="ispras"/></noinclude> |
== Постановка. == | == Постановка. == | ||
| Строка 15: | Строка 15: | ||
== NP!. == | == NP!. == | ||
Cертификат → собственно раскраска. | Cертификат → собственно раскраска. | ||
| − | + | ||
== Кого сводим к ней?.… == | == Кого сводим к ней?.… == | ||
| − | * | + | * 3ESAT |
* ''m'' дизъюнкций | * ''m'' дизъюнкций | ||
* ''n'' переменных. | * ''n'' переменных. | ||
| Строка 23: | Строка 23: | ||
== Строим граф. … == | == Строим граф. … == | ||
[[Image:3SAT-to-3Coloring.jpg|right|513px]] | [[Image:3SAT-to-3Coloring.jpg|right|513px]] | ||
| − | * Три вершины → метки 0, 1, 2. | + | * Три вершины → метки 0, 1, 2. → треугольник «a» |
| − | * Для каждого литерала по вершине → ''2n'' | + | * Для каждого литерала по вершине → ''2n'' → «б» → лепестки из узла «2» |
| − | * Для каждой дизъюнкции → ''7'' вершин → ''7m'' | + | * Для каждой дизъюнкции → ''7'' вершин → ''7m'' → «в» |
| − | ** ''3 + 2n + 7m'' вершин. | + | ** <m>l_1</m>, <m>l_2</m>, <m>l_3</m> ← литералы из скобки |
| + | * Итого → ''3 + 2n + 7m'' вершин. | ||
| + | |||
| + | == 3Color → 3ESAT .… == | ||
| + | |||
| + | [[Файл:3sat-to-3color.svg|800px|center]] | ||
| − | |||
| − | |||
| − | |||
| − | == .… == | + | == 3ESAT → 3Color .… == |
| − | + | [[Файл:3sat-to-3color-2.svg|800px|center]] | |
Текущая версия на 06:39, 3 марта 2022
- Заголовок
- Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Полнота/Vertex-3-Coloring
- Автор
- Стас Фомин
- Нижний колонтитул
- Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Полнота/Vertex-3-Coloring
- Дополнительный нижний колонтитул
- Стас Фомин, 06:39, 3 марта 2022
Содержание
Постановка.
Vertex Coloring.
Задача о раскраске вершин графа. Можно ли вершины неориентированного графа раскрасить в k цветов, так, чтобы соседние вершины имели разные цвета?
Vertex-3-Coloring.
Частный случай Vertex coloring для 3х цветов.
NP? .…
- ?
- Что будет сертификатом?
NP!.
Cертификат → собственно раскраска.
Кого сводим к ней?.…
- 3ESAT
- m дизъюнкций
- n переменных.
Строим граф. …
- Три вершины → метки 0, 1, 2. → треугольник «a»
- Для каждого литерала по вершине → 2n → «б» → лепестки из узла «2»
- Для каждой дизъюнкции → 7 вершин → 7m → «в»
- , , ← литералы из скобки
- Итого → 3 + 2n + 7m вершин.
3Color → 3ESAT .…
3ESAT → 3Color .…
