Классификация задач по сложности.

Задачи, как и алгоритмы принято классифицировать по сложности. Множество всех распознавательных задач, для которых существует полиномиальный разрешающий алгоритм, образуют класс Р. Ясно, что распознавательные трудноразрешимые задачи не принадлежат классу Р. Класс NP – это множество распознавательных задач, которые могут быть разрешены за полиномиальное время на недетерминированной машине Тьюринга (НМТ). Оракул предлагает решения, которые после проверки верификатором приобретают «юридическую» силу. Таким образом, задачи класса NP являются «полиноминально проверяемыми». Например, в задаче коммивояжера оракул предлагает некоторую перестановку всех вершин графа, а верификатор проверяет, образует ли эта перестановка гамильтонов цикл графа. Ясно, что такую проверку можно выполнить с полиномиальной сложностью – надо лишь проверить смежность соседних вершин. Построить одну перестановку вершин тоже можно с полиномиальной сложностью. Оба шага решения задачи полиномиальные, поэтому задача коммивояжера принадлежит классуNP. Трудноразрешимой ее делает факториальное число повторений этих шагов. Следует отметить, что такую двухшаговую процедуру поиска решения можно применить к любой распознавательной задаче полиномиальной сложности.

Соотношение между классами P и NP

Очевидно, что всякую ДМТ можно рассматривать как частный случай НМТ, в которой отсутствует стадия угадывания, а стадия проверки совпадает с ДМТ. Следовательно, справедливо включение P в NP. К настоящему времени не удалось доказать ни одного из более сильных утверждений: P = NP или P входит в NP Вопрос о соотношении классов P и NP поставлен более тридцати лет назад. Большинство специалистов полагают, что верно строгое включение P в NP. В самом деле, интуитивно класс P можно представить себе как класс задач, которые можно быстро решить, а класс NP – как класс задач, решение которых может быть быстро проверено. Ясно, что решить задачу намного труднее, чем проверить готовое решение. Поэтому наверняка в классе NP имеются задачи, которые нельзя решить за полиномиальное время. Более серьезной причиной полагать, что P ≠ NP, это существование NP-полных задач. Для того, чтобы доказать, что P ≠ NP необходимо научиться получать нижние оценки сложности любого алгоритма, предназначенного для решения некоторой задачи из класса NP. Поэтому проблему соотношения классов P и NP называют проблемой нижних оценок. Вопрос о соотношении классов P ≠ NP не праздный. На карту поставлено не только машинное время. Так, в криптографии существует раздел о шифровании с открытым ключом. Здесь намеренно используют задачи экспоненциальной сложности, которые не позволяют выполнить дешифрование информации за разумное время. Если вдруг P = NP, то возникает возможность существования для этих задач полиномиальных алгоритмов. Но тогда многие секреты перестанут быть секретными.

NP-полные задачи

Для некоторых задач класса P = NP было обнаружено удивительное свойство. Оказалось, что некоторые из них универсальны в том смысле, что построение полиномиального алгоритма для любой такой задачи влечет за собой возможность построения такого же алгоритма для всех остальных задач класса NP. Такие задачи называют NP-полными. Для понимания этого свойства требуется определить понятие полиномиальной сводимости одной задачи к другой. Пусть заданны две массовые задачи z1, z2 принадлежащие классу NP. Говорят, что задача z1полиномиально сводится к задаче z2, если • для любой частной задачи из z1 можно за полиномиальное время построить соответствующую ей частную задачу из z2; • решение построенной частной задачи из z2 за полиномиальное время может быть преобразовано в решение соответствующей частной задачи из z1. Массовую задачу z называют NP-полной, если любая задача из этого класса полиномиально сводится к решению задачи z. Таким образом, теперь ясно, что разработка полиномиального алгоритма любой NP-полной задачи практически означает возможность построения такого алгоритма для любой задачи класса NP, т. е. справедливость равенства P = NP. Для доказательства NP-полноты некоторой задачи, нет необходимости сводить к ней каждую задачу класса NP. Достаточно установить ее принадлежность к классу NP и показать, что к ней сводится какая-либо известная NP-полная задача. Чтобы воспользоваться этой схемой, надо иметь в распоряжении хотя бы одну NP-полную задачу. Методы, используемые при доказательстве NP-полноты конкретных задач, развиваются очень быстро. В настоящее время часто применяются три основных метода: сужение задачи, локальная замена и построение компоненты. Доказательство методом сужения NP-полноты задачи z1, которая принадлежит классу NP заключается в установление того, что задача z1 включает в качестве частного случая известную NP-полную задачу z2. Доказательство двумя другими методами достаточно нетривиальны, и поэтому здесь у нас нет возможности их рассмотреть и проиллюстрировать. В заключение следует отметить, что теория NP-полноты, помимо теоретического, представляет и чисто практический интерес. Доказав, что задача NP-полна, разработчик алгоритмов получает достаточное основания, чтобы отказаться от поиска эффективного и точного решения. В настоящее время для решения NP-полных задач используются в основном различного рода приближенные алгоритмы, основанные на эвристиках и вероятностных механизмах.