Блог

Выберите правильный оператор (ы):

• (A) Если X является NP-полной проблемой, то X является NP-проблемой
• (B) Если X является NP-полной задачей, то X является NP-сложной
• (C) Пусть X будет NP-полная задача. Если X полином может свести к задаче Y , то Y является NP-полным.
• (D) Пусть X будет NP-полная задача. Если Y полином может свести к задаче X , то Y является NP-полным.
• (E) Пусть X будет NP-полная задача. Если X полином может свести к задаче Y , то Y это NP-hard.

Мой ответ (A) (B) (C) (E):

• (A) (B) : X принадлежит NP-complete, означает, что X принадлежит NP и NP-hard
• (C) верно
• (D) Y может быть P, NP-жестким или NP-полным
• (E) Y является NP-полным, а также NP-жестким

Верен ли ответ?

Вот некоторые исправления:

(C) False. Y является NP-жестким, но не обязательно в NP.

(D) False. Y находится в NP, не обязательно NP-complete.

(E) Верно, но Y не обязательно является NP-полным.