Эффективная сертификация и определение NP - NP-полнота и вычислительная неразрешимость

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

Вспомните, что в главе 1, при первом знакомстве с задачей о независимом множестве, мы спрашивали: можно ли сказать хоть что-нибудь положительное о сложности задачи (с вычислительной точки зрения)? И действительно, кое-что положительное нашлось: если граф содержит независимое множество с размером не менее k, то этот факт можно легко доказать, представив такое независимое множество. Аналогичным образом, если экземпляр 3-SAT является выполнимым, это можно доказать, представив выполняющее присваивание. Поиск такого присваивания может быть невероятно сложной задачей, но после того, как сложная работа по его поиску будет завершена, остается подставить значения в условия и убедиться в том, что все они выполняются.

Здесь важен контраст между поиском решения и проверкой предложенного решения. Для задачи о независимом множестве или 3-SAT алгоритм поиска решений с полиномиальным временем нам неизвестен; однако проверка предлагаемого решения таких задач легко выполняется за полиномиальное время. Чтобы понять, что эта проблема не так уж тривиальна, представьте, какая проблема возникла бы, если бы потребовалось доказать невыполнимость экземпляра задачи 3-SAT. Какие “доказательства” можно было бы предъявить, чтобы убедить вас за полиномиальное время в невыполнимости задачи?

Задачи и алгоритмы

В этом заключена суть характеристики; теперь мы перейдем к ее формализации. Входные данные вычислительной задачи могут быть закодированы в виде конечной двоичной строки s. Длина строки s обозначается │s|. Задача принятия решения X будет описываться множеством строк, для которых возвращается ответ “да”. Алгоритм A для задачи принятия решения получает входную строку s и возвращает “да” или “нет” — это возвращаемое значение будет обозначаться A(s). Алгоритм A решает задачу X, если для всех строк s условие A(s) = да выполняется в том, и только в том случае, если s ∈ X.

Как обычно, мы говорим, что A имеет полиномиальное время выполнения, если существует такая полиномиальная функция p(∙), что для каждой входной строки s алгоритм A завершается для sне более чем за O(p│s│) шагов. До настоящего момента мы занимались задачами, которые решались за полиномиальное время. В приведенной выше записи этот факт можно выразить как множество P всех задач X, для которых существует алгоритм A с полиномиальным временем выполнения, решающий X.

Эффективная сертификация

Как же формализовать идею о том, что решение задачи может быть проверено эффективно независимо от того, насколько эффективно может решаться сама задача? Структура “алгоритма проверки” для задачи X отличается от структуры алгоритма, ищущего решение; для “проверки” решения необходима входная строка 5 и отдельная строка t (“сертификат”), доказывающая, что s является “положительным” экземпляром X.

Итак, алгоритм B называется эффективным сертифицирующим алгоритмом для задачи X, если он обладает следующими свойствами:

♦ B — алгоритм с полиномиальным временем, получающий два входных аргумента s и t;

♦ существует такая полиномиальная функция р, что для каждой строки s условие s ∈ X выполняется в том, и только в том случае, если существует строка t, для которой |t| ≤ P(|s|) и B(s, t) = да.

Чтобы понять, о чем в действительности говорит это определение, потребуется некоторое время. Эффективный сертифицирующий алгоритм следует рассматривать как подход к задаче X с “управленческой” точки зрения. Он не пытается самостоятельно решить, принадлежит ли входная строка s множеству X. Вместо этого он эффективно оценивает предлагаемые “доказательства” t, что s принадлежит X (при условии, что они не слишком длинные), и он является правильным алгоритмом в том слабом смысле, что s принадлежит X тогда, и только тогда, когда существует доказательство, которое его в этом убедит.

Эффективный сертифицирующий алгоритм B может использоваться как центральный компонент алгоритма “грубой силы” для задачи X: для входной строки s проверить все строки t длины ≤ P(|s|) и проверить, выполняется ли условие B(s, t) = да для каких-либо из этих строк. Однако существование B не дает никакого очевидного способа построения эффективного алгоритма, который решает X; в конце концов, мы еще должны найти строку t, для которой B(s, t) вернет ответ “да”, а количество возможностей для t экспоненциально велико.

NP: класс задач

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

(8.10) P ⊆ NP.

Доказательство. Рассмотрим задачу X ∈ P; это означает, что существует алгоритм с полиномиальным временем, который решает X. Чтобы показать, что X ∈ NP, необходимо показать, что существует эффективный сертифицирующий алгоритм B для X.

Сделать это очень просто; B строится по следующей схеме. При получении входной пары (s, t) сертифицирующий алгоритм B просто возвращает значение A(s). (Считайте B своего рода “прагматиком”, который игнорирует предложенное доказательство t и просто решает задачу своими силами.) Почему B является эффективным сертификатором для X? Очевидно, он выполняется с полиномиальным временем, как и A. Если строка s ∈ X, то для всех t длины не более p(|s|) имеем B(s, t) = да. С другой стороны, если s ∉ X, то для всех t длины не более p(|s|) имеем B(s, t) = нет. ■

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

♦ для задачи 3-SAT сертификат t является результатом присваивания булевых значений переменным; сертифицирующий алгоритм B проверяет заданное множество условий в соответствии с этим присваиванием;

♦ для задачи о независимом множестве сертификат t является описанием множества, содержащим не менее к вершин; сертифицирующий алгоритм B проверяет, что среди этих вершин нет двух, соединенных ребром;

♦ для задачи покрытия множества сертификат t представляет собой список к множеств из заданного набора; сертифицирующий алгоритм проверяет, что объединение этих множеств равно базовому множеству U.

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

(8.11) Присутствует ли в NP задача, не принадлежащая P? Возможно, P = NP? Вопрос о том, истинно равенство P = NP или нет, является фундаментальной проблемой в теории алгоритмов и одной из самых известных задач в современной теории вычислений. Общественное мнение склоняется к тому, что P ≠ NP, и это считается рабочей гипотезой в этой области, однако никаких убедительных технических свидетельств для этого нет. Скорее считается, что результат P = NP выглядит слишком невероятно, чтобы быть правдой. Неужели может существовать общее преобразование задачи проверки решения в куда более сложную задачу фактического поиска решения? Неужели могут существовать общие средства проектирования эффективных алгоритмов, достаточно мощных для решения всех этих сложных задач, которые почему-то не были обнаружены? На неудачные попытки разработки алгоритмов с полиномиальным временем для сложных задач в NP были потрачены колоссальные усилия; пожалуй, самое естественное объяснение всех этих повторяющихся неудач состоит в том, что эти задачи просто не могут быть решены за полиномиальное время.