Блог

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

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

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

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

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

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

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

Краткий ответ: Единственными 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-полной.