Рубрики

ВОРОТА | GATE-CS-2015 (набор 2) | Вопрос 65

Рассмотрим две задачи решения Q1, Q2, такие, что Q1 уменьшается за полиномиальное время до 3-SAT, а 3-SAT уменьшается за полиномиальное время до Q2. Тогда что из следующего согласуется с приведенным выше утверждением?
(A) Q1 находится в NP, Q2 труден в NP
(B) Q2 находится в NP, Q1 труден в NP
(C) Q1 и Q2 находятся в NP
(D) Q1 и Q2 находятся в NP hard

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

Q1 reduces in polynomial time to 3-SAT 
==> Q1 is in NP

3-SAT reduces in polynomial time to Q2 
==> Q2 is NP Hard.  If Q2 can be solved in P, then 3-SAT
    can be solved in P, but 3-SAT is NP-Complete, that makes 
    Q2 NP Hard

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

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

ВОРОТА | GATE-CS-2015 (набор 2) | Вопрос 65

0.00 (0%) 0 votes