P vs NP

P vs NP — это одна из центральных нерешённых задач в области теоретической информатики и математики, которая относится к вопросу о соотношении классов сложности P (Polynomial time) и NP (Non-deterministic Polynomial time). Формально задача ставится так: можно ли любую задачу, правильность решения которой проверяется за полиномиальное время (класс NP), также решить за полиномиальное время (класс P). Ответ на этот вопрос имеет фундаментальное значение для теории алгоритмов, криптографии, искусственного интеллекта и других дисциплин. Задача P vs NP считается одной из семи «задач тысячелетия», за решение которой Математический институт Клэя установил приз в один миллион долларов США.

Классы сложности P и NP

Определение P

Класс P (от англ. Polynomial) включает все задачи принятия решений, которые могут быть решены детерминированным алгоритмом (машиной Тьюринга) за время, ограниченное полиномом от размера входных данных. Иными словами, если размер задачи равен n, то время решения составляет O(nᵏ) для некоторой константы k. Примеры задач из класса P: проверка простоты числа, умножение матриц, задача о кратчайшем пути во взвешенном графе (алгоритм Дейкстры), поиск минимального остовного дерева (алгоритм Краскала), проверка связности графа.

Определение NP

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

Соотношение P и NP

Очевидно, что P ⊆ NP, так как если задачу можно решить за полиномиальное время, то её решение можно и проверить за полиномиальное время. Основной вопрос P vs NP заключается в том, выполняется ли обратное включение: NP ⊆ P. Если ответ положителен, то P = NP; если нет — P ≠ NP.

История задачи

Ранние работы

В 1956 году Джон фон Нейман в письме к Курту Гёделю затронул тему эффективности алгоритмов, но формальная постановка задачи была дана позже. В 1971 году канадско-американский учёный Стивен Кук в статье «Характеристика задач, допускающих эффективное решение, с помощью теорем Гёделя» сформулировал понятие NP-полноты и доказал, что задача SAT является NP-полной. Это стало отправной точкой для систематического изучения классов P и NP. Примерно в то же время, независимо от Кука, аналогичные идеи высказывал Леонид Левин (СССР) в своей статье 1973 года, где он ввёл понятие «задачи перебора» и доказал NP-полноту некоторых задач.

Развитие теории

В середине 1970-х годов Ричард Карп расширил список NP-полных задач, включив в него десятки прикладных проблем из комбинаторики и теории графов. К настоящему времени известно более 3000 NP-полных задач, среди которых задача о сумме подмножеств, задача коммивояжёра (TSP), задача о вершинном покрытии, задача о раскраске графа. В 1976 году Джон Хопкрофт и Джеффри Ульман выпустили фундаментальное учебное пособие «Введение в теорию автоматов, языков и вычислений», где закрепилась современная терминология.

NP-полнота

Определение

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

Примеры NP-полных задач

• Задача о выполнимости (SAT) — существует ли набор булевых переменных, обращающий заданную КНФ-формулу в истину?
• Задача о сумме подмножеств — можно ли выбрать подмножество заданных чисел так, чтобы их сумма равнялась заданному значению?
• Задача коммивояжёра (TSP) — существует ли маршрут в графе, посещающий все вершины ровно один раз и имеющий длину не больше заданной?
• Задача о клике — существует ли в графе полный подграф заданного размера?
• Задача о раскраске графа — можно ли раскрасить вершины графа в k цветов так, чтобы смежные вершины имели разные цвета?

NP-трудные задачи

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

Гипотезы и текущее состояние

Статус на 2025 год

На сегодняшний день задача P vs NP остаётся нерешённой. Большинство специалистов в области теоретической информатики склоняются к гипотезе, что P ≠ NP, хотя строгого доказательства этому нет. Основанием для такой гипотезы служит отсутствие полиномиальных алгоритмов для тысяч NP-полных задач, несмотря на десятилетия интенсивных исследований. Кроме того, известно, что для многих NP-полных задач (например, SAT) не существует алгоритмов, работающих быстрее экспоненциальных, при условии, что гипотеза экспоненциального времени (ETH) верна.

Попытки доказательства

За последние 50 лет неоднократно появлялись заявления о решении P vs NP, но все они оказались ошибочными или содержали логические пробелы. Наиболее известные из них: работа Виктора Киснера (Россия, 2010 год), статья Винай Деолаликара (Индия, 2020 год), а также более ранние попытки. Все они были опровергнуты научным сообществом. Математический институт Клэя в 2010 году включил эту задачу в список «проблем тысячелетия», но официально ни одно из предложенных решений не было принято.

Барьеры для доказательства

Существуют три основных подхода к решению, каждый из которых сталкивается с серьёзными препятствиями:

• Релятивизация (диагонализация с оракулами). В 1975 году Тед Бейкер, Джон Гилл и Роберт Соловей показали, что существуют оракулы, при которых P = NP и P ≠ NP одновременно, что делает простые диагонализационные доказательства невозможными.
• Естественные доказательства (natural proofs). В 1994 году Разборов и Рудич предположили, что любой метод доказательства, основанный на естественных комбинаторных принципах, не сможет ответить на вопрос для широкого класса схем.
• Алгебраизация (algebratization). В 2008 году Ааронсон и Вигдерсон обобщили предыдущие ограничения.

Значение и практические последствия

При P = NP

Если бы оказалось, что P = NP, это имело бы революционные последствия для многих областей:

• Криптография с открытым ключом (RSA, ECC) была бы взломана за полиномиальное время.
• Робототехника и планирование получили бы точные алгоритмы для задач навигации и логистики.
• Искусственный интеллект мог бы эффективно решать задачи формального вывода и проверки гипотез.
• Биоинформатика — быстрое сворачивание белков и анализ геномов.

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

При P ≠ NP

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

Связанные понятия

Класс co-NP

Класс co-NP включает задачи, ответ на которые «нет» может быть проверен за полиномиальное время. Вопрос о соотношении co-NP и P также открыт; известно, что P ⊆ co-NP ∩ NP.

Класс PSPACE

Класс PSPACE охватывает задачи, решаемые с полиномиальными затратами памяти (но не обязательно времени). Задачу P vs NP можно рассматривать как частный случай более общей проблемы о соотношении временной и пространственной сложности.

Задачи с различными подходами

• Задача о раскраске графа — для двудольных графов решается за линейное время, а для трёхцветных — NP-полна.
• Задача о сумме подмножеств — существует псевдополиномиальный алгоритм с использованием динамического программирования (О(n·S), где S — сумма чисел).

Интересные факты

• В 2002 году индийский математик Маниндха Агравал вместе с коллегами доказал, что проверка простоты числа принадлежит классу P (алгоритм AKS). До этого этот результат считался близким к NP-полноте.
• Понятие «NP-полнота» было независимо открыто Стивеном Куком и Леонидом Левиным; в советских источниках NP-полные задачи иногда называют «задачами перебора».
• Ежегодно в научных журналах публикуется несколько сотен статей, так или иначе связанных с вопросом P vs NP.
• По состоянию на 2025 год точное неравенство P ≠ NP не доказано, но для подавляющего большинства исследователей это является рабочей гипотезой.

Источники

• Cook S. A. «The complexity of theorem-proving procedures» (1971).
• Levin L. A. «Universal search problems» (1973).
• Karp R. M. «Reducibility among combinatorial problems» (1972).
• Baker T., Gill J., Solovay R. «Relativization of the P = NP problem» (1975).
• Razborov A. A., Rudich S. «Natural proofs» (1994).
• Aaronson S., Wigderson A. «Algebrization: a new barrier in complexity theory» (2008).
• Агравал М., Каял Н., Саксена Н. «PRIMES is in P» (2002).
• Математический институт Клэя. Официальное описание проблемы «P vs NP» (2000).