EssayAI
Блог
Блог
Естественные науки

Классы P и NP: проверка решения и сложность поиска

8 ноября 2026Время чтения: 8 минут
#классы P и NP#теория сложности#полиномиальное время#NP-полнота#алгоритмы
Классы P и NP: проверка решения и сложность поиска

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

Что измеряют классы сложности

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

Для определения P и NP рассматривают задачи разрешения: для каждого входа нужно ответить «да» или «нет». Например: «Есть ли в графе клика хотя бы из kk вершин?» Клика - множество вершин, каждая пара которых соединена ребром. Сам граф и число kk вместе составляют вход. Вопрос о максимальном размере клики является задачей оптимизации; он тесно связан с задачей разрешения, но формально это разные постановки.

Оценка полиномиальна, если время ограничено некоторым многочленом от длины входа: например, nn, n2n^2 или n10n^{10}. Показатель степени фиксирован для алгоритма и не растёт вместе с nn. Это математический критерий, а не гарантия удобства: алгоритм за n100n^{100} шагов может быть непрактичным, а экспоненциальный алгоритм иногда успешно работает на небольших данных.

При росте n золотой маркер для числа наборов 2ⁿ удаляется от маркера квадратичной оценки n²; вертикальная шкала показывает десятичный логарифм числа шагов.

Класс P: быстро решить задачу

P - класс задач разрешения, для которых существует детерминированный алгоритм, всегда выдающий правильный ответ за полиномиальное время в худшем случае. «Существует» важно: речь идёт не о скорости конкретной программы, а о наличии хотя бы одного алгоритма с такой гарантией для всех входов.

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

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

Класс NP: быстро проверить свидетель

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

Для клики свидетель - список kk вершин. Проверяющий убеждается, что вершины различны и каждая пара соединена ребром. Достаточно проверить k(k−1)/2k(k-1)/2 пар; это полиномиальное число проверок. Если такая клика существует, её список подтвердит ответ «да». Если нет, ни один список проверку не пройдёт.

Свидетель не обязательно легко найти. Само слово NP происходит от nondeterministic polynomial time: недетерминированная машина может выбрать ветвь вычисления, соответствующую свидетельству, и проверить её за полиномиальное время. Это математическая модель, а не утверждение, что обычный компьютер способен бесплатно перебрать все ветви одновременно.

Свойство NP асимметрично: оно обещает короткое проверяемое подтверждение для ответов «да», но не обязательно для ответов «нет». Класс задач, для которых так подтверждаются ответы «нет», называют co-NP. Неизвестно, совпадают ли NP и co-NP.

Почему P содержится в NP

Если задача уже решается за полиномиальное время, проверяющий может проигнорировать свидетель и просто запустить алгоритм решения. Поэтому всегда известно включение P⊆NPP \subseteq NP. Вопрос в том, строгое ли оно: есть ли в NP задача, которую никакой детерминированный полиномиальный алгоритм не решает?

Равенство P=NPP=NP означало бы существование полиномиальных алгоритмов для всех задач NP. Неравенство P≠NPP\ne NP означало бы, что хотя бы одна задача с быстро проверяемыми свидетельствами не имеет такого алгоритма. По данным Института Клэя, вопрос остаётся открытым. Большинство специалистов ожидают неравенства, но ожидание не заменяет доказательства.

Перебор и рост числа вариантов

Пусть в булевой формуле nn переменных. Для каждой есть два значения, поэтому всего возможных наборов 2n2^n. При n=10n=10 это 10241024 набора; для сравнения, n2=100n^2=100. При n=20n=20 получаем уже 1 048 5761\,048\,576 и 400400. Эти значения можно воспроизвести ползунком выше.

Графики n в квадрате и двух в степени n на логарифмической шкале: при n равно 10 получаются 100 и 1024
Графики n в квадрате и двух в степени n на логарифмической шкале: при n равно 10 получаются 100 и 1024

Перебор формулы способен по очереди проверять наборы, пока не найдёт подходящий или не исчерпает все варианты. Но сравнение 2n2^n с n2n^2 не доказывает, что другого, более хитрого алгоритма не существует. К тому же nn здесь обозначает число переменных, а в определениях классов измеряется длина полного входа, включая запись формулы. Перевод между этими величинами нужно оговаривать в каждом доказательстве.

NP-полнота и направление сведения

Задача является NP-полной, если она принадлежит NP и к ней полиномиально сводится любая задача из NP. Сведение преобразует вход задачи AA во вход задачи BB так, чтобы ответы совпадали: «да» превращается в «да», а «нет» - в «нет». Преобразование само должно выполняться за полиномиальное время.

Чтобы доказать NP-полноту новой задачи BB, обычно сначала описывают её свидетель и проверку, а затем сводят к ней уже известную NP-полную задачу AA: A≤pBA \leq_p B. Направление принципиально: быстрый алгоритм для BB после преобразования решил бы AA. Обратное сведение само по себе трудность BB не устанавливает.

Классический пример - SAT, задача о выполнимости булевой формулы. Теорема Кука - Левина утверждает, что SAT NP-полна; формальное изложение есть в описании проблемы P против NP Стивена Кука. Если хотя бы одну NP-полную задачу решить за полиномиальное время, полиномиальные сведения дадут такие алгоритмы для всех задач NP, и получится P=NPP=NP.

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

Что это меняет на практике

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

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

В криптографии важна сложность типичных экземпляров и конкретные предположения о задаче. Из одного лишь P≠NPP\ne NP не следует автоматически надёжность любой криптосистемы: утверждение о худшем случае не гарантирует трудность случайных входов.

Частые ошибки

  • «NP означает неполиномиальная». Нет: название связано с недетерминированным полиномиальным временем; все задачи P принадлежат NP.
  • «NP-полная задача обязательно требует экспоненциального времени». Такой нижней границы для произвольных алгоритмов пока не доказано.
  • «Быстрая проверка подтверждает и да, и нет». Для NP гарантировано свидетельство ответа «да»; для «нет» это отдельный вопрос.
  • «Сведение можно направить как угодно». Для доказательства трудности новой задачи известную трудную задачу сводят именно к новой.

FAQ

P равно NP?

Неизвестно. Доказано P⊆NPP \subseteq NP, но равенство и строгость включения пока не установлены.

Входит ли сортировка в P?

Сортировка возвращает последовательность, а P определён для задач с ответом «да» или «нет». Связанные вопросы разрешения, например упорядочены ли данные, имеют полиномиальные алгоритмы.

Если проверка ответа быстрая, почему поиск может быть долгим?

Проверка получает кандидат извне. Поисковому алгоритму ещё нужно выбрать его среди возможных кандидатов. Для некоторых задач известен быстрый поиск, а для NP-полных универсальный полиномиальный алгоритм пока не найден.

Коротко

P объединяет задачи разрешения с полиномиальным алгоритмом решения, NP - задачи с полиномиально проверяемым свидетельством ответа «да». Известно P⊆NPP \subseteq NP, а равенство открыто. NP-полнота связывает трудность задач через полиномиальные сведения; большой размер полного перебора сам по себе не доказывает отсутствие другого алгоритма.

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Задача о клике: пример и поиск в графе

Задача о клике: пример и поиск в графе

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

8 ноября 20268 минут
Алгоритм LZ77: сжатие с помощью ссылок назад

Алгоритм LZ77: сжатие с помощью ссылок назад

Алгоритм LZ77 на пошаговом примере: как скользящее окно находит повторы, что означают расстояние и длина, как работает перекрытие и от чего зависит размер результата.

8 ноября 20268 минут
Числа Белла: разбиения множества и формула

Числа Белла: разбиения множества и формула

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

8 ноября 20269 минут
Числа трибоначчи: формула и примеры вычисления

Числа трибоначчи: формула и примеры вычисления

Числа трибоначчи: три начальных значения, рекуррентная формула и расчёт по шагам. Как последовательность считает пути по ступенькам и как написать эффективный алгоритм.

8 ноября 20269 минут
Чётность подстановки: инверсии и знак

Чётность подстановки: инверсии и знак

Чётность подстановки через инверсии, транспозиции и циклы: пошаговый подсчёт, доказательство независимости разложения и применение в алгоритмах и определителях.

8 ноября 20268 минут
Дерево двоичного поиска: построение и операции

Дерево двоичного поиска: построение и операции

Дерево двоичного поиска: как устроены узлы, как построить BST по ключам, выполнить обход и удалить элемент, от чего зависит высота и сложность операций.

8 ноября 20268 минут