Инструменты пользователя

Инструменты сайта


examination:saod:question43

Полиномиальная сводимость задач. NP-полная задача

Отформатировать (разбить на абзацы)

Понятие сложности задач

Под задачей понимается некоторый вопрос, на который нужно найти (вычислить) ответ. Задачи бывают массовыми (общими) и частными (индивидуальными).

Общая задача определяется:
• списком параметров – свободных переменных, конкретные значения которых неопределенны;
• формулировкой условий – свойств, которыми должен обладать ответ (решение задачи).

Массовые задачи часто называют алгоритмическими проблемами. Частная задача получается из массовой, если всем параметрам массовой задачи придать конкретные значения – здесь исходные данные. В общем случаи для любой алгоритмически разрешимой задачи существует несколько разрешающих алгоритмов.

С практической точки зрения важно не просто существование разрешающих алгоритмов, а поиск среди них наиболее простого и наименее трудоемкого. Под сложностью задачи принято понимать минимальную из сложностей алгоритмов, решающих эту задачу. Компьютерные науки пока не накопили достаточно сведений для того, чтобы задача минимизации сложности алгоритма была поставлена математически строго. Поэтому без ответов остаются такие вопросы, связанные с нижней оценкой сложности алгоритмов, а значит, и сложности задач:
• Существует ли для заданной задачи алгоритм минимальной сложности?
• Как убедиться, что найденный алгоритм действительно минимальный или, напротив, не минимальный?
• Можно ли для рассматриваемой задачи доказать, что никакой разрешающий ее алгоритм не может быть проще найденной нижней оценки сложности?

При разработке алгоритмов можно наблюдать, что для некоторых задач можно построить алгоритм полиномиальной сложности. Такие задачи называют полиномиальными. Полиноминально разрешимые задачи можно успешно решать на компьютере и даже в тех случаях, когда они имеют большую размерность. Для других задач не удается найти полиномиальный алгоритм. поэтому их называют трудноразрешимыми. К классу трудноразрешимых задач относится большое число задач алгебры, математической логики, теории графов, теории автоматов и других разделов дискретной математики. В большинстве своем это так называемые переборные задачи. Переборная задача характеризуется экспоненциальным множеством вариантов, среди которых нужно найти решение, и может быть решена алгоритмом полного перебора. Переборный алгоритм имеет экспоненциальную сложность и может хорошо работать только для небольших размеров задачи. С ростом размера задачи число вариантов быстро растет, и задача становится практически неразрешимой методом перебора. Многие из переборных задач являются экспоненциальными по постановке. Экспоненциальные по постановке задачи не представляют особого интереса для теории алгоритмов, поскольку для них, очевидно, невозможно получить алгоритм полиномиальной сложности. Возникает вопрос: если известно, что некоторая задача алгоритмически разрешима, то неудача в разработке для нее полиномиального разрешающего алгоритма является следствием неумения конкретного разработчика или следствием каких-то свойств самой задачи? Ответ на этот вопрос дает классическая теория алгоритмов, которая классифицирует задачи по сложности. При этом классифицируются лишь распознавательные задачи – задачи, имеющие распознавательную форму. В распознавательной форме суть задачи сводится к распознаванию некоторого свойства, а ее решение – один из двух ответов: «да» или «нет». С точки зрения математической логики задаче распознавания свойства соответствует предикат Р(х), где х – множество фактических значений входных переменных задачи. Существуют задачи, которые изначально имеют распознавательную форму. Например, являются ли два графа изоморфными? Другой пример – задача о выполнимости булевой функции, которая является исторически первой распознавательной задачей, глубоко исследованной в теории алгоритмов. Многие задачи, которые в исходной постановке представлены в иной форме (к ним относятся задачи дискретной оптимизации), довольно просто приводятся к распознавательной форме. Например, если требуется найти хроматическое число графа, то формулируют вопрос: верно ли, что заданный граф является k – раскрашиваемый, где k – заданное целое положительное число. Между тем, имеются задачи, которые нельзя привести к распознавательной форме. Это. В первую очередь, конструктивные задачи – задачи на построение объектов дискретной математики, обладающих заданными свойствами: генерация всех подмножеств конечного множества; генерация всех n! Различных перестановок; построение плоской укладки графа; построение остовного дерева графа и т. п. Такие задачи могут быть как трудноразрешимыми, так и полиноминально разрешимыми. Они пока не попадают под существующую в теории алгоритмов классификацию.

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

Задачи, как и алгоритмы принято классифицировать по сложности. Множество всех распознавательных задач, для которых существует полиномиальный разрешающий алгоритм, образуют класс Р. Ясно, что распознавательные трудноразрешимые задачи не принадлежат классу Р. Класс 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-полных задач используются в основном различного рода приближенные алгоритмы, основанные на эвристиках и вероятностных механизмах.

examination/saod/question43.txt · Последние изменения: 2014/01/15 08:21 (внешнее изменение)