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

Slide Show

Заголовок

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

Автор

Стас Фомин

Нижний колонтитул

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

Дополнительный нижний колонтитул

Стас Фомин, 06:38, 3 марта 2022

Постановка.

3SAT.

3SAT или «3-Выполнимость» — частный случай задачи SAT, в которой все дизъюнкции имеют не более чем три терма.

Однако, показано, что несмотря на это ограничение, 3SAT является NP-полной задачей.

3ESAT.

Частный случай 3SAT, когда в каждой скобке ровно три литерала.

NP?.…

•  ?
• Что будет сертификатом?

NP!.

Cертификат → вектор, на котором формула истинна.

Кого сводим к ней?.…

• 3SAT
• Проблемы:
  • Скобки из
    • одного литерала
    • двух литералов

Один литерал в скобке-дизъюнкции. …

• 3-КНФ может быть истинна ←→ ;
  • проверяем, что
  • иначе → сразу невыполнима.
• Подстановка
  • Выкидываем
    • все дизъюнкции, содержащие литерал
    • все литералы ,
    • выполнимость получившейся КНФ равносильна выполнимости исходной
• Повторяем, пока не избавимся от дизъюнкций из одного литерала.

Два литерала в скобке-дизъюнкции. …

• дизъюнкцию 3-КНФ заменяем на две:
  • .
• → .

разумеется, три разных литерала! Т.е. нельзя , можно

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

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

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