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

Версия 22:26, 21 декабря 2011

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

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