NP-сложные проблемы, которые не являются NP-полными, сложнее?

Question

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

Значит ли это, что NP-сложные задачи, которые не являются NP-полными, сложнее? А как сложнее?

Answer 1

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

(i) решение проблемы,
(ii) число решений задачи должно быть конечным, и каждое решение должно иметь полиномиальную длину, и
(iii) учитывая решение по полиномиальной длине, мы должны быть в состоянии сказать, является ли ответ на задачу да / нет

Теперь легко заметить, что может быть много сложных для NP задач, которые не относятся к установленной NP и которые сложнее решить. В качестве интуитивно понятного примера, оптимизационная версия коммивояжера, в которой нам нужно найти фактическое расписание, сложнее, чем вариант решения коммивояжера, где нам просто нужно определить, существует ли расписание с длиной <= k или нет. *

Answer 2

Проблема остановки машины Тьюринга неразрешима на машинах Тьюринга и NP-харде, но не у NPC.Видимо, это сложнее;)

Answer 3

Проблема остановки Тьюринга неразрешима и относится к набору NP-Hard. Для решения проблемы остановки у нас нет какого-либо решения, так как это язык RE. Поэтому у нас нет алгоритма для его решения. Таким образом, ясно, что неразрешимые проблемы также есть в NP-Hard. Таким образом, набор NP-Hard также содержит языки или проблемы, для которых у нас нет алгоритма для решения.

Answer 4

Множество NP-сложных задач является расширенным набором NP-полных задач. Есть классы сложности, более «сложные», чем NP, например, PSPACE , EXPTIME или EXPSPACE , и все они содержат NP-сложные, но не NP-полные проблемы .

Answer 5

1. NP-полный должен быть NP и NP-hard.
2. и NP-hard, не являющиеся NP-полными, не являются NP.
3. Теперь по определению NP есть кто-то, кто дает пример ответа на проблему. и есть верификатор для проверки.
4. это означает, что у NP-Hard нет ни одного из них. Следовательно, их трудно решить, это правда.

Answer 6

С http://en.wikipedia.org/wiki/NP-hard#Examples

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