Рубрики

ВОРОТА | GATE-CS-2005 | Вопрос 58

Рассмотрим следующие две проблемы на неориентированных графах

α : Given G(V, E), does G have an independent set of size | V | - 4?
β : Given G(V, E), does G have an independent set of size 5? 

Что из следующего является ИСТИННЫМ?

(A) α находится в P, а β NP-полна
(B) α является NP-полным и β находится в P
(C) и α, и β являются NP-полными
(D) и α, и β находятся в P

Ответ: (с)
Объяснение: Задача решения, не зависящая от графа, является NP Complete.
Тест на этот вопрос

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

ВОРОТА | GATE-CS-2005 | Вопрос 58

0.00 (0%) 0 votes