Почему класс NP-Complete важен по сравнению с NP-hard?

Я изучаю вычислительную сложность, и мне было интересно, почему проблемы NP-Complete (NPC) вообще являются важным классом. Я нахожу очевидным, почему мы заинтересованы в том, чтобы показать, что данная проблема NP трудна для NP.

Я также понимаю определение NPC, и то, что показать конкретное решение проблемы сложно с точки зрения NP, зная, что оно есть в NP, это именно то, что нужно NPC.

Однако я не понимаю, почему эта концепция так важна? Конечно, если мы находим любую NP-жесткий алгоритм , который работает во время P (независимо от того , или нет , что в НП), мы показали , что .$NP = P$

Почему эта концепция так важна?

Есть по крайней мере несколько причин, по которым NPC интересен:

• Класс NP содержит много интересных задач (как практических, так и теоретических), более того, многие из этих проблем оказываются NP-сложными (и, следовательно, NP-полными), но многие проблемы вне NP почти наверняка слишком сложны для решения. это больше, чем теоретический интерес , поэтому NPC предоставляет (грубую) группу проблем, которые кажутся сложными, но не настолько сложными, что мы не можем попытаться что-то с ними сделать.
  Другими словами, NPC, вероятно, является пределом того, что, как мы можем надеяться, может быть решаемо за полиномиальное время, и кажется, что попытка PSPACE = P (например) будет натянутой.
• Класс NP является конструктивно интересным. Это основной пример того, «получаем ли мы больше вычислительной« скорости »от недетерминизма». Таким образом, нас интересует, P = NP или нет, и NPC (вероятно) является важным компонентом разработки этого.
• NP-hard (как класс) действительно слишком большой и разнообразный, чтобы иметь дело с ним как с одной вещью, это все, что можно свести к проблеме NP-complete , включая огромную массу вещей вне NP, так что с точки зрения С точки зрения попыток разработать общие результаты и методы, нет ничего, за что можно ухватиться.

С точки зрения того, кто пишет код для жизни, хорошее знакомство с NP-полнотой важно для:

1. Распознавание, когда вы лаете не на то дерево

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

2. Нахождение правильного дерева

Поскольку компьютеры часто используются для атаки на NP-сложные задачи, были разработаны специализированные решатели, которые могут эффективно решать некоторые NP-сложные задачи. Признание того, что ваша проблема является NP-полной, является первым шагом к поиску существующего инструмента (SAT, ILP, SMT, CSP и т. Д.), Который может помочь вам найти точные решения в некоторых случаях, когда вам в противном случае пришлось бы согласиться на приближение.

«Конечно, если мы найдем какой-нибудь NP-сложный алгоритм, который работает во время P (независимо от того, находится ли он в NP), мы показали, что NP = P. Почему эта концепция так важна?»

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