Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Полнота/Vertex-3-Coloring — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «<slideshow incmark="…" headingmark="." scaled=1 style="ispras"/> == Постановка. == === Vertex Coloring. === {{:Vertex coloring}} === Vertex-3-Colori…») |
StasFomin (обсуждение | вклад) |
||
| Строка 8: | Строка 8: | ||
{{:Vertex 3 coloring}} | {{:Vertex 3 coloring}} | ||
| − | == NP?… == | + | == NP? .… == |
* ? | * ? | ||
| Строка 18: | Строка 18: | ||
== Кого сводим к ней?.… == | == Кого сводим к ней?.… == | ||
* 3SAT | * 3SAT | ||
| − | |||
* ''m'' дизъюнкций | * ''m'' дизъюнкций | ||
* ''n'' переменных. | * ''n'' переменных. | ||
== Строим граф. … == | == Строим граф. … == | ||
| + | [[Image:3SAT-to-3Coloring.jpg|right|513px]] | ||
* ''7m+2n+3'' вершин. | * ''7m+2n+3'' вершин. | ||
| − | + | * Пометим три вершины числами 0, 1, 2. | |
| − | + | * Пометим каждым литералом (переменной или ее отрицанием) по одной вершине. | |
| + | * Остальные ''7m'' вершин разобьем на группы по 7, каждая группа соответствует одной из дизъюнкций. | ||
| − | |||
| − | |||
* a) → вершины 0, 1 и 2 соединены между собой ребрами. | * a) → вершины 0, 1 и 2 соединены между собой ребрами. | ||
* б) показаны еще ''n'' треугольников в этом графе. | * б) показаны еще ''n'' треугольников в этом графе. | ||
| − | * | + | * в) показывает, как соединены ребрами вершины, соответствующие каждой дизъюнкции. На этом рисунке l1,l2,l3 обозначают литералы, входящие в дизъюнкцию. |
| + | |||
| + | == .… == | ||
| + | |||
| + | Число раскрасок в 3 цвета кратно 6: перестановка цветов сохраняет правильную раскраску. | ||
Версия 02:41, 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ертификат → собственно раскраска.
Кого сводим к ней?.…
- 3SAT
- m дизъюнкций
- n переменных.
Строим граф. …
- 7m+2n+3 вершин.
- Пометим три вершины числами 0, 1, 2.
- Пометим каждым литералом (переменной или ее отрицанием) по одной вершине.
- Остальные 7m вершин разобьем на группы по 7, каждая группа соответствует одной из дизъюнкций.
- a) → вершины 0, 1 и 2 соединены между собой ребрами.
- б) показаны еще n треугольников в этом графе.
- в) показывает, как соединены ребрами вершины, соответствующие каждой дизъюнкции. На этом рисунке l1,l2,l3 обозначают литералы, входящие в дизъюнкцию.
.…
Число раскрасок в 3 цвета кратно 6: перестановка цветов сохраняет правильную раскраску.