Рубрики

ВОРОТА | GATE CS 2012 | Вопрос 4

Assuming P != NP, which of the following is true ?
(A) NP-complete = NP
(B) NP-complete  P = 
(C) NP-hard = NP
(D) P = NP-complete

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

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

Ответ B (ни одна NP-полная задача не может быть решена за полиномиальное время). Потому что, если одна проблема NP-Complete может быть решена за полиномиальное время, то все проблемы NP могут быть решены за полиномиальное время. Если это так, то NP и P множество становятся одинаковыми, что противоречит данному условию.

Связанная статья:
НП-Полнота | Комплект 1 (Введение)
P против NP проблема (Википедия)
Тест на этот вопрос

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

ВОРОТА | GATE CS 2012 | Вопрос 4

0.00 (0%) 0 votes