Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Полнота/Vertex-3-Coloring

Slide Show

Заголовок

Полиномиальные сводимости и 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 .…

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.