Рубрики

ВОРОТА | GATE-CS-2014- (Set-1) | Вопрос 48

Предположим, обнаружен алгоритм полиномиального времени, который правильно вычисляет наибольшую клику в данном графе. В этом сценарии, что из следующего представляет правильную диаграмму Венна классов сложности P, NP и NP Complete (NPC)?


(А) А
(Б) Б
(С) С
(D) D

Ответ: (D)
Объяснение: Клика — это полная проблема NP. Если одна проблема полного NP может быть решена за полиномиальное время, то все они могут быть. Таким образом, набор NPC становится равным P.
Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE-CS-2014- (Set-1) | Вопрос 48

0.00 (0%) 0 votes