2011-gre-cs-practice-book.pdf/Q11 — различия между версиями

Версия 16:08, 18 декабря 2024

Вопрос: 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»

Справка: NP-hard это NP-сложные, а NP-complete это NP-полные.

Взглянем на картинку и разберем:

1. если задача A в классе NP-полных и для нее существует полиномиальный алгоритм, то действительно P=NP, так как для всего NP тоже существует полиномиальный алгоритм
2. если задача B в NP, но необязательно в классе NP-полных и для нее существует полиномиальный алгоритм, то все равно есть задачи из класса NP-полных, поэтому равенство P=NP не выполняется
3. Если A лежит в классе NP-полных и для нее существует полиномиальный алгоритм, то и для всего NP тоже существует полиномиальный алгоритм, то есть для B тоже Решено: Urmat A 16:08, 18 декабря 2024 (UTC)