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

Question

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

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

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

31

computer-science complexity-theory p-np

Источник

user460208 28 сен '10 в 05:26

6 ответов

Другие вопросы по тегам computer-science complexity-theory p-np

user676057 18 июн '11 в 16:41 2011-06-18 16:41 · Answer 1 · 2011-06-18 16:41

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

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

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

user752150 19 июн '11 в 05:18 2011-06-19 05:18 · Answer 2 · 2011-06-19 05:18

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

10

Источник

user752150 19 июн '11 в 05:18

user186019 14 окт '10 в 11:06 2010-10-14 11:06 · Answer 3 · 2010-10-14 11:06

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

7

Источник

user186019 14 окт '10 в 11:06

user1660417 10 сен '12 в 14:20 2012-09-10 14:20 · Answer 4 · 2012-09-10 14:20

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

user1778828 12 дек '12 в 07:16 2012-12-12 07:16 · Answer 5 · 2012-12-12 07:16

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

user432433 28 сен '10 в 05:35 2010-09-28 05:35 · Answer 6 · 2010-09-28 05:35

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

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