Теорема о разделении

Теорема о разделении — в теории сложности вычислений фундаментальное утверждение, устанавливающее взаимосвязь между классами сложности P и NP. В наиболее распространённой формулировке (теорема Ладнера) она утверждает, что если P ≠ NP, то существуют языки (задачи), которые не принадлежат классу P и не являются NP-полными, то есть занимают промежуточное положение между этими двумя классами. Теорема о разделении, доказанная Ричардом Ладнером в 1975 году, является одним из ключевых результатов теории сложности, поскольку она показывает, что гипотеза P ≠ NP не влечёт за собой того, что все задачи из NP, не входящие в P, обязательно являются NP-полными.

Формулировка

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

Теорема Ладнера (теорема о разделении): Если P ≠ NP, то существует язык (задача) L, такой что:

1. L ∈ NP;
2. L ∉ P;
3. L не является NP-полным.

Иными словами, при условии P ≠ NP класс NP имеет нетривиальную иерархию: в нём существуют задачи, которые сложнее, чем задачи из P, но проще, чем NP-полные задачи.

Доказательство (основная идея)

Доказательство Ладнера конструктивно и основано на методе диагонализации с использованием понятия «полиномиально-временной ступенчатой функции» (полиномиально-временной иерархии). Идея состоит в построении языка L, который «медленно» растёт по сложности, чередуя этапы, на которых он ведёт себя как задача из P, и этапы, на которых он ведёт себя как задача, не являющаяся NP-полной.

Конкретно, строится последовательность натуральных чисел (ступеней), определяющих моменты времени, когда машины Тьюринга, пытающиеся решить L, должны либо остановиться с ответом «да», либо продолжить вычисления. Язык L определяется так, что:

• Если на некотором шаге машина Тьюринга, которая могла бы решить L за полиномиальное время, останавливается, то L устроен так, чтобы эта машина ошиблась (тем самым L ∉ P).
• Если на некотором шаге машина Тьюринга, которая могла бы свести произвольную задачу из NP к L, останавливается, то L устроен так, чтобы это сведение было некорректным (тем самым L не является NP-полным).

Доказательство использует технику «задержек» (delays) и «подсказок» (oracles), чтобы гарантировать, что L не слишком прост и не слишком сложен.

Следствия и значение

1. Структура класса NP

Теорема о разделении показывает, что класс NP не является двухэлементным (P и NP-полные задачи) при условии P ≠ NP. Существует континуум возможных степеней сложности внутри NP, образующих так называемую иерархию Ладнера. Это означает, что задача может быть «чуть сложнее» P, но «чуть проще» NP-полной.

2. Отсутствие полной классификации

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

3. Связь с гипотезой P ≠ NP

Теорема Ладнера не доказывает и не опровергает гипотезу P ≠ NP. Она лишь показывает, что если эта гипотеза верна, то структура NP богаче, чем просто два класса. Если же P = NP, то теорема тривиальна (все NP-задачи принадлежат P, и промежуточных задач нет).

4. Применение в других классах

Аналоги теорем о разделении существуют для других классов сложности, например, для классов EXP и NEXP, а также для классов с оракулами. В общем случае, для любых двух классов сложности, один из которых строго больше другого, можно построить задачу, лежащую между ними, если выполнены определённые условия (например, классы замкнуты относительно полиномиального сведения).

Примеры задач, предположительно являющихся промежуточными

Хотя теорема Ладнера гарантирует существование таких задач, она не даёт явных примеров. Однако на практике к числу задач, которые, как полагают, могут быть промежуточными (при условии P ≠ NP), относят:

• Задача изоморфизма графов (Graph Isomorphism): неизвестно, является ли она NP-полной или принадлежит P. Существуют субэкспоненциальные алгоритмы, но полиномиальный алгоритм не найден.
• Факторизация целых чисел (Integer Factorization): задача разложения числа на простые множители. Известно, что она принадлежит NP и к ней сводится задача изоморфизма графов, но её NP-полнота не доказана. В отличие от многих NP-полных задач, для факторизации существуют квантовые алгоритмы (алгоритм Шора), работающие за полиномиальное время.
• Дискретное логарифмирование (Discrete Logarithm): задача нахождения показателя степени в конечном поле. Аналогична факторизации по сложности.

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

Критика и ограничения

• Конструктивность: Доказательство Ладнера даёт конструкцию языка L, но эта конструкция не является «естественной» в том смысле, что построенный язык искусственен и не соответствует реальным вычислительным задачам. Поэтому теорема не даёт практических указаний на то, какие конкретные задачи являются промежуточными.
• Зависимость от гипотезы: Теорема справедлива только при условии P ≠ NP. Если P = NP, то утверждение тривиально (промежуточных задач нет).
• Ограничения метода: Доказательство использует диагонализацию, которая в некоторых контекстах (например, для классов с оракулами) может быть неэффективной. Существуют оракулы, при которых P ≠ NP, но промежуточных задач нет (так называемые «оракулы Ладнера»).

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

• Теорема Ладнера была доказана в 1975 году, когда Ричард Ладнер работал в Корнеллском университете. Она стала одним из первых результатов, систематически исследующих структуру класса NP.
• Название «теорема о разделении» происходит от того, что она «разделяет» класс NP на три непересекающиеся части: P, NP-полные задачи и промежуточные задачи.
• В 1980-х годах были получены обобщения теоремы для других классов сложности, например, для классов с полиномиальной иерархией (теорема Шёнинга).
• Существует также понятие «NP-промежуточных задач» (NP-intermediate), которое прямо связано с теоремой Ладнера.