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

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

(8.10) P N NP.

Доказательство.

Рассмотрим задачу X P; это означает, что существует ал-

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

алгоритм B для X.

Сделать это очень просто; B строится по следующей схеме. При получении входной пары (5, t) сертифицирующий алгоритм B просто возвращает значе- ние A(5). (Считайте B своего рода «прагматиком», который игнорирует пред- ложенное доказательство t и просто решает задачу своими силами.) Почему B является эффективным сертификатором для X? Очевидно, он выполняется с по- линомиальным временем, как иA. Если строка 5 X, то для всех t длины не более />(|s|) имеем B(s, t) = да. С другой стороны, если 5 ⅜X, то для всех t длины не более />(|s|) имеем B(5, 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 были потрачены колоссальные усилия; пожалуй, самое естественное объяснение всех этих повторяющихся неудач состоит в том, что эти задачи просто не могут быть решены за полиномиальное время.

8.4.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме NP: класс задач:

  1. Школьный класс
  2. ПЕРВЫЙ КЛАСС
  3. ПЯТЫЙ КЛАСС
  4. Одиночки в классе
  5. 5. Критическая теория и рабочий класс.
  6. 6.3. Женщина высшего класса
  7. Глава 13. INTJ «Компетентность + независимость = высший класс»
  8. ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
  9. Масса, демократия и рабочий класс
  10. СРАВНИТЕЛЬНАЯ СИСТЕМА КЛАССОВ