NP-полнота и неразрешимость

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

Definition

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

Scope

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

Core questions

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

Key concepts

• класс сложности P
• класс сложности NP
• полиномиальное приведение
• NP-трудность
• NP-полнота
• теорема Кука-Левина
• булева выполнимость (SAT)
• проблема P против NP

Key theories

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

Теорема Кука-Левина доказывает, что проблема выполнимости булевых формул (SAT) является NP-полной: каждая задача в NP сводится к ней за полиномиальное время, предоставляя первую NP-полную задачу и основу для доказательства сложности других.

Сводимость среди комбинаторных задач

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

Clinical relevance

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

History

Стивен Кук ввел понятие NP-полноты в 1971 году, доказав NP-полноту SAT; Леонид Левин независимо получил аналогичные результаты. Статья Ричарда Карпа 1972 года показала, что 21 естественная задача является NP-полной, установив охват этой концепции. Книга Гэри и Джонсона 1979 года каталогизировала сотни NP-полных задач и стала стандартным справочником.

Debates

P против NP

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

Key figures

• Stephen Cook
• Richard Karp
• Leonid Levin
• Michael Garey
• David Johnson

Seminal works

• cook1971
• karp1972
• cormen2009

Frequently asked questions

В чем разница между NP-трудной и NP-полной задачей?

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

Означает ли NP-полнота, что задача никогда не может быть решена?

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