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

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

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

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