Ограничения мощи алгоритмов. Недетерминистический алгоритм, страница 2

В то время как описанный выше подход принимает во внимание размер выхода задачи, информационно-теоретический подход пытается установить нижнюю границу алгоритма на основе количества информации, которую он производит.

Ограничения мощи алгоритмов

При изучении вычислительной сложности задач первое, на что смотрят и ученые и практики в области информатики, – может ли данная задача быть разрешена при помощи некоторого алгоритма за полиномиальное время. Определение 1. Алгоритм решает задачу за полиномиальное время, если его временная эффективность в наихудшем случае принадлежит классу О(p(n)), где p(n) – полином от размера входных данных n. Задачу, которая может быть решена за полиномиальное время, будем называть легкой, а задачу, которая не может быть решена за полиномиальное время, – трудной.

Ограничения мощи алгоритмов

Говоря нестрого, задачи, решаемые за полиномиальное время, можно рассматривать как множество, которые ученые-теоретики в области информатики называют P. Более формальное определение включает в P только задачи принятия решения, представляющие собой задачи, ответ на которые – «да» либо «нет». Определение 2. Класс P представляет класс задач принятия решения, которые могут быть решены (детерминистическим) алгоритмом за полиномиальное время. Этот класс задач называется полиномиальным.

Ограничения мощи алгоритмов

Естественно задаться вопросом: может ли каждая задача принятия решения быть решена за полиномиальное время? Оказывается, нет. В действительности некоторые задачи принятия решения не могут быть решены вообще, никаким алгоритмом. Такие задачи называются неразрешимыми. Это знаменитая задача останова: для данной компьютерной программы и входных данных написать программу, которая бы определила, завершится ли выполнение исходной программы или она будет выполняться бесконечно.

Ограничения мощи алгоритмов

Существуют ли задачи разрешимые, но трудные? Да, но количество известных примеров невелико, в особенности тех, которые возникают естественным путем, а не построены в качестве теоретического доказательства. Однако имеется большое количество важных задач, для которых не найден алгоритм с полиномиальным временем работы, но и не доказана невозможность его существования. Общее у всех этих задач то, что они обладают экспоненциальным (или еще более быстрым) ростом количества вариантов выбора решения с ростом размера задачи n.

Ограничения мощи алгоритмов

Определения 3. Недетерминистическим алгоритмом называется двухэтапная процедура, которая получает в качестве входа экземпляр I задачи принятия решения и делает следующее. Недетерминистический этап («угадывания»): генерируется произвольная строка S, которая может рассматриваться как кандидат в решение данной задачи I (но может оказаться и полной ерундой). Детерминистический этап («проверки»): детерминистический алгоритм получает I и S в качестве входных данных и выдает «да», если S представляет собой решение экземпляра I. (Если S не является решением I, алгоритм либо возвращает «нет», либо может вообще не завершить работу.)

Ограничения мощи алгоритмов

Определение 4. Класс NP – это класс задач принятия решения, которые могут быть решены недетерминистическим полиномиальным алгоритмом. Этот класс задач называется недетерминистическим полиномиальным. Наиболее важный открытый вопрос теоретической информатики: является ли класс P истинным подмножеством класса NP или на самом деле оба эти класса совпадают?

Ограничения мощи алгоритмов

Определение 5. Задача принятия решения D1 называется полиномиально приводимой к задаче принятия решения D2, если имеется функция t, которая преобразует экземпляры D1 в экземпляры D2 так, что 1. t отображает все экземпляры D1 с положительным ответом, и все экземпляры D1 с отрицательным ответом на экземпляры D2 с отрицательным ответом. 2. t вычислима при помощи алгоритма с полиноминальным временем работы.

Ограничения мощи алгоритмов

Определение 6. Задача принятия решения D является NP-полной если 1. она принадлежит классу NP; 2. любая задача а NP полиномиально приводима к D.