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

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

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

[[Категория:Решенные задачи]]