Что такое NP-complete в информатике?

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

2 351
language-agnostic theory algorithm mathematical-optimization np-complete

2 ответа:

NP расшифровывается как недетерминированный полинома времени.

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

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

Edit: как отмечали другие, часто существуют аппроксимационные решения для NP-полных задач. В этом случае аппроксимационное решение обычно дает аппроксимацию, используя специальную нотацию, которая говорит нам, насколько близка аппроксимация.

178

Что это NP?

NP-это множество всех решение проблемы (вопросы с ответом " да " или "нет"), для которых " да " -ответы могут быть проверен в полиномиальное время (O (nk), где n это размер проблемы, и k является константой) по a детерминированная машина Тьюринга. Полиномиальное время иногда используется в качестве определения быстро или быстро.

Что это P?

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

Что это NP-Complete?

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

другими словами:

  1. x находится в NP, и
  2. каждая проблема в NP-это приводи х

Итак, что же делает NP-Complete так интересно, что если какая-либо из NP-полных проблем должна была быть решена быстро, то все NP проблемы могут быть решены быстро.

Смотрите также пост что такое " P=NP?- а почему это такой знаменитый вопрос?

366