Рубрики

ВОРОТА | GATE-CS-2009 | Вопрос 13

Пусть pA — проблема, принадлежащая классу NP. Тогда что из следующего является ИСТИННЫМ?
(A) Не существует алгоритма полиномиального времени для pA
(B) Если pA можно решить детерминистически за полиномиальное время, то P = NP
(C) Если pA является NP-сложным, то оно NP-полное.
(D) рА может быть неразрешимым.

Ответ: (с)
Объяснение:

Если проблема является как NP трудной, так и NP, то это NP Complete. См. Http://espressocode.top/np-completeness-set-1/ для деталей.

Тест на этот вопрос

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

ВОРОТА | GATE-CS-2009 | Вопрос 13

0.00 (0%) 0 votes