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

Материал из DISCOPAL
Перейти к: навигация, поиск
 
Строка 1: Строка 1:
−
{{reserve-task|[[Участник:Urmat A|Urmat A]] 16:08, 18 декабря 2024 (UTC)}}
 
−
 
 
== Вопрос: Q11-08c765 ==
 
== Вопрос: Q11-08c765 ==
  

Текущая версия на 20:48, 18 декабря 2024

Вопрос: Q11-08c765

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

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

Ответы

  • только 1
  • только 2
  • только 1 и 2
  • Правильный ответ: только 1 и 3
  • 1, 2 и 3


Объяснение

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

NPstuff.png

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

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

  1. если задача A в классе NP-полных и для нее существует полиномиальный алгоритм, то действительно P=NP, так как для всего NP тоже существует полиномиальный алгоритм
  2. если задача B в NP, но необязательно в классе NP-полных и для нее существует полиномиальный алгоритм, то все равно есть задачи из класса NP-полных, поэтому равенство P=NP не выполняется
  3. Если A лежит в классе NP-полных и для нее существует полиномиальный алгоритм, то и для всего NP тоже существует полиномиальный алгоритм, то есть для B тоже
Источник — «https://discopal.ispras.ru/index.php?title=2011-gre-cs-practice-book.pdf/Q11&oldid=34001»