2004-gre-cs-practice-book.pdf/Q69

Ссылки сюда (1) →

Вопрос: Q69-4c9f66

Предположим, что Q и R — языки.

Предполагая, что , что из следующего следует, что R отсутствует в P?

Ответы

• R находится в NP
• Q находится в NP, а Q за полиномиальное время сводится к R
• Q находится в NP, а R за полиномиальное время сводится к Q
• Q является NP-полным, а R за полиномиальное время сводится к Q
• Правильный ответ: Q является NP-полным, а Q за полиномиальное время сводится к R

Объяснение

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

• «R находится в NP» — ну может и в P быть при этом. (шутка про «NP=неП»), не катит.
• «Q находится в NP, а Q за полиномиальное время сводится к R» — Q тоже может быть в P, не катит.
• Cводимость задачи мало говорит о ее сложности, для сложности к ней надо свести сложную задачу → не катит:
  • «Q находится в NP, а R за полиномиальное время сводится к Q»
  • «Q является NP-полным, а R за полиномиальное время сводится к Q»
• «Q является NP-полным, а Q за полиномиальное время сводится к R» — то что надо, NPC — класс реально сложных задач, за пределом P, и если из нее сводится к R, то да, это заражает R сложностью и выводит ее из P.

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

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

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