Рубрики

Алгоритмы | NP Complete | Вопрос 3

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

(D) X может быть неразрешимым.

Ответ: (с)
Объяснение: (A) неверно, потому что набор NP включает в себя как P (разрешимое за полиномиальное время), так и NP-Complete.
(B) неверно, потому что X может принадлежать P (та же причина, что и (A))
(C) правильно, потому что NP-полный набор является пересечением NP и Hard-наборов.
(D) неверно, потому что все проблемы NP разрешимы в конечном наборе операций.
Тест на этот вопрос

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

Алгоритмы | NP Complete | Вопрос 3

0.00 (0%) 0 votes