Рубрики

ВОРОТА | GATE-CS-2003 | Вопрос 12

Рама и Шьяма попросили показать, что определенная проблема NP является NP-полной. Рам показывает уменьшение полиномиального времени от задачи 3-SAT до Π, а Шиам показывает уменьшение полиномиального времени с Π до 3-SAT. Что из следующего может быть выведено из этих сокращений?
(A) NP NP-сложный, но не NP-полный
(B) in находится в NP, но не является NP-полным
(C) NP является NP-полным
(D) Π не является NP-сложным, ни в NP

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

Так как полиномиальное сокращение времени от Π до 3-SAT возможно, оно NP-Complete.
Тест на этот вопрос

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

ВОРОТА | GATE-CS-2003 | Вопрос 12

0.00 (0%) 0 votes