Рубрики

ВОРОТА | GATE IT 2006 | Вопрос 10

Проблема в NP является NP-полной, если

(A) Его можно свести к задаче 3-SAT за полиномиальное время
(B) Задача 3-SAT может быть сведена к ней за полиномиальное время
(C) Его можно свести к любой другой проблеме в NP за полиномиальное время
(D) некоторая проблема в NP может быть сведена к нему за полиномиальное время

Ответ: (Б)
Объяснение: проблема в NP становится NPC, если все проблемы NP можно свести к ней за полиномиальное время. Это то же самое, что свести к минимуму любую проблему NPC. 3-SAT, являющаяся проблемой NPC, сведение ее к проблеме NP означает, что проблема NPC — это NPC.

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

ВОРОТА | GATE IT 2006 | Вопрос 10

0.00 (0%) 0 votes