Рубрики

Алгоритмы | NP Complete | Вопрос 5

Какие из следующих утверждений являются ИСТИННЫМИ?
(1) Проблема определения того, существует ли цикл в неориентированном графе, находится в P.
(2) Задача определения, существует ли цикл в неориентированном графе, находится в NP.
(3) Если задача A является NP-полной, существует недетерминированный алгоритм полиномиального времени для решения A.
(А) 1, 2 и 3
(Б) 1 и 3
(С) 2 и 3
(D) 1 и 2

Ответ: (А)
Объяснение: 1 верно, потому что обнаружение цикла может быть сделано за полиномиальное время с использованием DFS (см. Это ).
2 верно, потому что P является подмножеством NP.
3 справедливо потому , что NP также полное подмножество NP и NP означает N на детерминированной Р olynomial времени решение существует. (См. Это )
Тест на этот вопрос

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

Алгоритмы | NP Complete | Вопрос 5

0.00 (0%) 0 votes