Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/3КНФ→Клика (сохраняя число решений)

Материал из DISCOPAL
< Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC‎ | Задачи
Версия от 08:40, 11 марта 2021; StasFomin (обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Получите сводимость как в Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/3КНФ→Клика, но дополнительно требуется, чтобы количество решений сохранялось.

Т.е. если 3КНФ F полиномиально преобразуется в (граф G, число k), то количество выполняющих наборов переменных для F равно количеству клик размера k в графе G).

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

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

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