2011-gre-cs-practice-book.pdf/Q11

Задача зарезервирована: Urmat A 15:52, 18 декабря 2024 (UTC)

Вопрос: Q11-08c765

Предположим, что задача A является NP-полной, а задача B находится в NP, но не обязательно NP-полной. Какое из следующих утверждений обязательно верно?

1. . Полиномиальный алгоритм для A подразумевает P = NP.
2. . Полиномиальный алгоритм для B подразумевает P = NP.
3. . Полиномиальный алгоритм для A подразумевает полиномиальный алгоритм для B

Ответы

1. только 1
2. только 2
3. только 1 и 2
4. только 1 и 3
5. 1, 2 и 3

Объяснение

Исходники — вопрос 11 на 20 странице книги «2011-gre-cs-practice-book.pdf»

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.