Как некоторые NP-полные проблемы могут быть NP-Hard?

Я пытаюсь объединить мои услышанные вокруг P, NP, NP-Complete и NP-Hard интуитивно, так что мне не нужно запоминать их определения.

На следующем изображении (левый сценарий, P!= NP) имеется перекрывающая область между NP-Complete и NP-Hard. Означает ли это, что некоторые проблемы являются NP-Complete и NP-Hard? Я считаю, что это противоречиво, в соответствии с этим конкретным ответом: Каковы различия между NP, NP-Complete и NP-Hard?.

В приведенной выше ссылке говорится, что проблема NP-Complete проверяется полиномиальным временем, а проблема NP-Hard - нет. Итак, как может быть перекрытие?

enter image description here

Ответы

Ответ 1

Часть определения NP-полноты является NP трудной. Поэтому каждая NP-полная проблема NP-hard. Это также отражается на обоих ваших графиках.

Ответ 2

Таблица, с которой вы связались, была неправильной, пока я не исправил ее несколько часов назад. NP-полные проблемы - это подмножество NP-проблем, и все проблемы NP проверяются по полиномиальному времени по определению. Проблемы с NP-трудностью - это те проблемы, которые по крайней мере столь же сложны, как и любая другая проблема NP (что является неинтуитивным, поскольку проблемы, не связанные с NP, могут быть NP-жесткими). ​​

Чтобы быть NP-Complete, проблема должна быть

  • в NP
  • NP-трудной

чтобы быть полным в определенном классе сложности, проблема должна быть

  • в этом классе сложности
  • по крайней мере так же сложно, как и любая другая проблема в классе сложности

Мы должны определить "по крайней мере, как трудно". Предположим, что мы имеем задачу А в NP. Чтобы доказать, что это NP-жесткий (и, следовательно, NP-Complete), мы покажем, что все задачи в NP могут быть преобразованы в в полиномиальное время. Поскольку A принимает хотя бы полиномиальное время для решения, и полиномы закрываются при добавлении, преобразование теперь ничтожно, а время выполнения такое же, как время выполнения A (в терминах это является полиномиальным или нет).

Как только у вас возникнет одна проблема NP-Complete, вы можете доказать, что проблема NP в NP NP-hard (и, следовательно, NP-Complete), взяв еще одну NP-полную проблему B и преобразуя ее в в полиномиальное время.

Надеюсь, это даст понять, что NP-Complete - это подмножество NP-hard (и что таблица, с которой вы связаны, была неправильной).