Алгоритмы | NP Complete | вопрос 2

Пусть S — NP-полная задача, а Q и R — две другие проблемы, которые неизвестны в NP. Q сводится за S за полиномиальное время, а S сводится к R. за полиномиальное время. Какое из следующих утверждений верно? (GATE CS 2006)
(A) R является NP-полным
(B) R является NP-сложным
(C) Q является NP-полным
(D) Q — NP-сложный

Ответ: (Б)
Объяснение: (A) Неправильно, потому что R отсутствует в NP. NP Полная задача должна быть как в NP, так и в NP-сложности.
(B) Верно, потому что NP Полная задача S полиномиально обучаема R.
(C) Неправильно, потому что Q не в NP.
(D) Неправильно, потому что не существует NP-полной задачи с полиномиальным временем, сводимой по Тьюрингу к Q.
Тест на этот вопрос

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

Алгоритмы | NP Complete | вопрос 2

0.00 (0%) 0 votes