Отображение NP, NP-полноты или NP-жесткости

Правильно ли я понимаю эти три категории?

Чтобы показать, что проблема X является NP:

  1. Покажите, что X можно проверить детерминистически за полиномиальное время (или X разрешимо с помощью НТМ)

Чтобы показать, что проблема X является NP-полной:

  1. Покажите, что X можно проверить детерминистически за полиномиальное время (или X разрешимо с помощью NTM)
  2. Покажите, что для известной задачи NP-C L, L ≤p X
  3. Покажите, что для известной NP-C-задачи L X ≤p L (Обязателен ли этот шаг? Если да, то чем отличается чисто NP-сложная задача от NP-C-задачи?)

Чтобы показать, что проблема X является NP-сложной:

  1. Покажите, что для известной задачи NP-C L, L ≤p X

algorithm np
person user    schedule 30.04.2015    source источник

Ответы (1)


arrow_upward
7
arrow_downward

Ты почти понял.

Учитывая проблему X, чтобы показать, что это NPC, вам не нужно показывать X ≤p L, для некоторых проблем с NPC L.

На самом деле это гарантировано, так как вы уже показали, что X находится в NP (в 1), и вы знаете, что L является NP-полным. По определению NP-Complete это означает полиномиальное сокращение времени от ВСЕХ проблем в NP до L, в том числе от X, поэтому в основном ваш шаг (3) в доказательстве NPC является избыточным.

Более элегантный способ показать утверждения о том, что нужно сделать, чтобы доказать каждое свойство:

Чтобы показать, что X является NP:

  1. Покажите, что X можно проверить детерминистически за полиномиальное время (или X разрешимо с помощью НТМ)

Чтобы показать, что X является NP-Hard:

  1. Покажите, что для известной NP-сложной задачи L, L ≤p X

OR

  1. Покажите, что для любой задачи L в NP L ≤p X (на самом деле это делается только один раз, для SAT, и является определением NP-Hard).

Чтобы показать, что проблема X является NP-полной:

  1. Show X - это NP-Hard
  2. Показать X в NP
person amit    schedule 30.04.2015