Что делает NP-сложную проблему не быть NP-полной проблемой?

Question

У меня путаница с NP-сложными проблемами.
Некоторые NP-сложные проблемы есть в NP, которые называются NP-Complete, а некоторые нет в NP.
Например: проблема остановки - только NP-сложная, а не NP-полная.
Но почему он не NP-полный? Я имею в виду, какое свойство должна иметь проблема, чтобы квалифицироваться как
"NP-сложная, но не NP-полная проблема"?

Answer 1

Я думаю, что самый короткий ответ: NP-complete = NP-hard AND в NP.

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

Что касается проблемы остановки, она не может быть в NP, и, следовательно, не является NP-полной.

Answer 2

Что определяет NP, так это то, что вы можете проверить решение проблемы NP за полиномиальное время.Таким образом, если проблема NP-сложная, но не NP-полная, вы не можете проверить решение проблемы теоретически своевременно.Это имеет смысл, если вы посмотрите на проблему остановки.Решением может быть «да» или «нет», что можно проверить только путем повторного решения исходной проблемы, то есть ее нет в NP.

Answer 3

NP-hard просто означает «по крайней мере так же сложно, как и проблема в NP».NP-complete означает «в NP все проблемы NP-complete могут быть сведены к этой проблеме, и эта проблема может быть сведена ко всем задачам NP-complete».

Статья в Википедии , вероятно,хорошая отправная точка, так как она конкретно говорит о проблеме остановки как одной из ее иллюстраций.

Answer 4

Краткий ответ: Единственными NP-сложными проблемами, которые не являются NP-полными, являются те, которые не являются частью NP.

Длинный ответ:

Теперь, почему это? Давайте внимательно посмотрим на определение NP-полного и NP-сложного:

Задача X является NP-полной, если:

1. Находится в NP

2. Каждая задача в NP сводится к X за полиномиальное время.

Задача X является NP-сложной, если она удовлетворяет (2) ((1) не является обязательным условием).

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

Например, все NP-сложные проблемы, которые не являются проблемами решения, не являются NP-полными (поскольку NP по определению формируется с проблемами решения). В частности, поисковая версия задачи коммивояжера: С учетом списка городов и их попарных расстояний задача состоит в том, чтобы найти кратчайший из возможных маршрутов, который посещает каждый город ровно один раз и возвращается в исходный город.

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

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