NP-полнота и редукции

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

Definition

Задача является NP-полной, если она принадлежит классу NP и любая задача из NP сводится к ней с помощью полиномиальной редукции; такие задачи являются максимально сложными элементами NP, эквивалентными друг другу с точностью до эффективного преобразования.

Scope

Эта тема охватывает класс NP задач, проверяемых за полиномиальное время, полиномиальные редукции типа «многие к одному», теорему Кука–Левина, устанавливающую NP-полноту задачи выполнимости, каталог NP-полных комбинаторных задач Карпа и методологию доказательства NP-полноты новых задач путем редукции от известных.

Core questions

• Что значит для задачи быть одной из самых сложных в NP?
• Как теорема Кука–Левина определяет первую NP-полную задачу?
• Как редукции используются для доказательства NP-полноты новой задачи?
• Почему NP-полнота одной задачи имеет последствия для тысяч других?

Key theories

Теорема Кука–Левина

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

Редукции Карпа и сеть NP-полных задач

Карп показал, что двадцать одна естественная задача, от раскраски графов до задачи коммивояжера, являются NP-полными с помощью полиномиальных редукций, что положило начало практике установления сложности через растущую сеть редукций.

Clinical relevance

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

History

Кук доказал NP-полноту задачи выполнимости в 1971 году, а Левин независимо получил эквивалентные результаты в Советском Союзе. В 1972 году Карп продемонстрировал двадцать одну дополнительную NP-полную задачу, выявив повсеместность этого явления и сделав NP-полноту центральным инструментом для диагностики вычислительной сложности.

Key figures

• Stephen Cook
• Leonid Levin
• Richard Karp

Seminal works

• cook1971
• karp1972

Frequently asked questions

Что означает NP?

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

Как доказать, что новая задача является NP-полной?

Необходимо показать две вещи: что задача находится в NP, то есть кандидатные решения быстро проверяемы, и что некоторая известная NP-полная задача сводится к ней за полиномиальное время. Редукция переносит известную сложность, помещая новую задачу в число самых сложных в NP.