Обсуждение:Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/Vcover-clique — различия между версиями
Материал из DISCOPAL
(Новая страница: «Обе задачи являются NP-полными([http://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BA%D0%BB%D0%B8%D0%BA%D0%B5], [ht...») |
(нет различий)
|
Текущая версия на 21:42, 13 июня 2011
Обе задачи являются NP-полными([1], [2]) Поэтому по определению NP-полноты они полиномиально сводятся друг к другу.