Почему NP-хард не равен NP-полному?
Мое неформальное понимание используемых определений:
NP - все задачи, которые можно проверить за полиномиальное время
NP-complete - все задачи NP и NP-сложные
NP-сложный - по крайней мере, такой же сложный, как и самая сложная задача в NP
Проблема решения - проблема, которая задает вопрос относительно ввода и выводит логическое значение.
Путаница:
Проблема с неизвестным решением P vs NP возникает из того факта, что мы не можем доказать или опровергнуть все проблемы в NP, которые могут быть решены за полиномиальное время. Похоже, что аналогичный вопрос возникает в отношении NP-Complete vs NP-hard. Откуда мы знаем, что все проблемы в NP-hard не могут быть проверены за полиномиальное время и, следовательно, приводят к NP-hard = NP-complete?
Вот мои рассуждения
Судя по онлайн-исследованиям, различие кажется, что это как-то связано с проблемами принятия решений (концепция, с которой я новичок, но кажется достаточно простой). Я думаю, это означает, что проблемы в NP имеют дополнительные проблемы решения, которые спрашивают, является ли ввод решением проблемы. Допустим, проблема в том, чтобы найти оптимальное решение. Я считаю, что проблема дополнительного решения заключается в том, «является ли данный вход оптимальным решением?», И я считаю, что если эта проблема решения поддается проверке за полиномиальное время, то проблема является NP-полной (или в NP). Таким образом, это означает, что NP-сложные проблемы, которые не являются NP-полными проблемами, - это проблемы, которые либо не имеют проблемы с решением (что, я считаю, никогда не бывает правдой, поскольку любое решение грубой силы может ответить на это), либо проблема является NP-сложной, а не NP -полный, если у него есть проблема с решением, которая не поддается проверке за полиномиальное время. Если последнее, то похоже, что у нас та же проблема, что и у P vs NP. То есть, как мы можем подтвердить, что все задачи решения в NP-hard не имеют решений за полиномиальное время?
Извините, если приведенная выше фраза выглядит странно. Я постараюсь прояснить любую путаницу в моем вопросе.
примечания
Меня интересуют как интуитивное объяснение, так и формальное объяснение (доказательство, если это сложный ответ). Формальное объяснение, безусловно, может быть ссылкой на научную статью. Я не хочу, чтобы кто-то тратил много времени на слишком сложное доказательство, которое может выходить за рамки моего понимания (я обнаружил, что теория сложности очень быстро становится ... сложной).
Если это поможет для объяснения, я работал над проблемой коммивояжера, и в настоящее время я работаю над документом по проблеме планирования медсестер (я считаю, что это NP-сложные задачи).
