Что такое NP-полный в информатике?

Question

Что такое NP-полная проблема? Почему это такая важная тема в информатике?

Answer 1

Я слышал объяснение, а именно: " NP-Полнота, вероятно, является одной из самых загадочных идей при изучении алгоритмов. «NP» означает «недетерминированное полиномиальное время» и является названием того, что называется классом сложности, к которому могут относиться проблемы. Важной особенностью класса сложности NP является то, что проблемы в этом классе могут быть проверены с помощью алгоритма полиномиального времени. В качестве примера рассмотрим проблему подсчета вещей. Предположим, на столе куча яблок. Проблема в том, сколько там яблок? Вам предоставляется возможный ответ 8. Вы можете проверить этот ответ за полиномиальное время, используя алгоритм подсчета яблок. Подсчет яблок происходит за O (n) (это обозначение Big-oh), потому что для подсчета каждого яблока требуется один шаг. Для n яблок нужно n шагов. Эта проблема в классе сложности NP.

Проблема классифицируется как NP-полная , если можно показать, что она является NP-Hard и проверяемой за полиномиальное время. Не вдаваясь слишком глубоко в обсуждение NP-Hard, достаточно сказать, что есть определенные проблемы, решения которых за полиномиальное время не были найдены. То есть требуется что-то вроде n! (n факториал) шаги для их решения. Однако, если вам дано решение проблемы NP-Complete, вы можете проверить это за полиномиальное время.

Классическим примером проблемы NP-Complete является проблема коммивояжера. "

Автор: ApoxyButt От: http://www.everything2.com/title/NP-complete

Answer 2

NP Проблема: -

1. Проблема NP - это такая проблема, которая может быть решена за недетерминированный полиномиальный промежуток времени.
2. Недетерминированный алгоритм работает в два этапа.
3. Стадия недетерминированного угадывания && Стадия недетерминированной проверки.

Тип проблемы Np

1. NP завершено
2. NP Hard

NP Полная задача: -

1 Решение Решение A называется NP complete, если оно имеет следующие два свойства: -

1. Относится к классу NP.
2. Любая другая проблема в NP может быть преобразована в P за полиномиальное время.

Некоторые примеры: -

• проблема с рюкзаком
• проблема подмножества сумм
• проблема покрытия вершин

Answer 3

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

Answer 4

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

проблема NP-Complete - это NP, но также, если вы можете решить ее за полиномиальное время (называемое P), тогда все проблемы NP - P.

Так что хрен.