Пусть 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 | Вопрос 6
- Алгоритмы | NP Complete | Вопрос 3
- Алгоритмы | NP Complete | Вопрос 1
- Алгоритмы | NP Complete | Вопрос 5
- Алгоритмы | NP Complete | Вопрос 4
- Алгоритмы | Анализ алгоритмов (рецидивов) | Вопрос 9
- Алгоритмы | Анализ алгоритмов (рецидивов) | Вопрос 8
- Алгоритмы | Анализ алгоритмов (рецидивов) | Вопрос 7
- Алгоритмы | Анализ алгоритмов (рецидивов) | Вопрос 3
- Алгоритмы | Анализ алгоритмов (рецидивов) | Вопрос 6
- Алгоритмы | Анализ алгоритмов (рецидивов) | Вопрос 4
- Алгоритмы | Анализ алгоритмов (рецидивов) | Вопрос 11
- Алгоритмы | Анализ алгоритмов (рецидивов) | вопрос 2
- Алгоритмы | Анализ алгоритмов (рецидивов) | Вопрос 11
- Алгоритмы | Анализ алгоритмов (рецидивов) | Вопрос 1
0.00 (0%) 0 votes