Рубрики

ВОРОТА | Gate IT 2008 | Вопрос 11

Для задач X и Y Y является NP-полной и X сводится к Y за полиномиальное время. Что из перечисленного правда?
(A) Если X можно решить за полиномиальное время, то и Y
(B) X является NP-полным
(C) X NP-жесткий
(D) X находится в NP, но не обязательно NP-завершено

Ответ: (D)
Объяснение:

Чтобы решить этот тип вопросов в GATE, мы дадим 2 важные теоремы. Доказательства этого выходят за рамки этого объяснения. Для доказательства, пожалуйста, обратитесь к разделу Введение в алгоритмы Томаса Кормена.

Теорема — 1
Когда конкретная трудная задача (NPC, NPH и неразрешимые проблемы) сводится к неизвестной проблеме за полиномиальное время, тогда неизвестная проблема также становится трудной.

Когда проблема NPC (NP-Complete) сводится к неизвестной проблеме, неизвестная проблема становится NPH (NP-Hard).

  Когда проблема NPH (NP-Hard) сводится к неизвестной проблеме, неизвестная проблема становится NPH (NP-Hard).

Когда неразрешимая проблема сводится к неизвестной проблеме, неизвестная проблема также становится неразрешимой.

Помните, что сложные задачи необходимо преобразовать для этой теоремы, но не иначе.

Теорема — 2

Когда неизвестная проблема сводится к простой задаче (P или NP) за полиномиальное время, тогда неизвестная проблема также становится легкой.

  Когда неизвестная проблема сводится к проблеме P-типа, неизвестная проблема также становится P.

Когда неизвестная проблема сводится к проблеме типа NP, неизвестная проблема также становится NP.

Помните, что неизвестные проблемы нужно преобразовать, чтобы эта теорема работала, но не иначе.

В данном вопросе неизвестная задача X сводится к задаче NPC за полиномиальное время, поэтому теорема 1 не будет работать. Но все проблемы NPC также являются NP, поэтому мы можем сказать, что X сводится к известной проблеме NP, так что теорема 2 применима, и X также является NP. Чтобы сделать его NPC, мы должны сначала доказать, что это NPH, что не так, поскольку Y не уменьшается до X.

Это решение предоставлено Пранджул Ахаджа .

 

Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | Gate IT 2008 | Вопрос 11

0.00 (0%) 0 votes