11. Задачи распознавания. Переход от оптимизационной задачи к задаче распознавания

Имеются различия между двумя аспектами труднорешаемости.

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

Первые примеры труднорешаемых задач были построены в 60^х годах, а в 70^х было показано, что большое количество реальных задач относится к труднорешаемым. В число этих задач вошло большое количество задач из теории автоматов, формальной теории языков и математической логики. Однако большинство труднорешаемых практических задач в действительности разрешимы. Более того, они разрешимы за полиномиальное время с помощью недетерминированного вычислительного устройства.

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

Помимо поисков методов доказательства труднорешаемых задач ведутся работы по сравнению сложности различных задач. Основной метод доказательства того, что две задачи близки, состоит в “сведении” их друг к другу с помощью конструктивного преобразования. Оно отображает любую индивидуальную задачу первого типа в эквивалентную ей индивидуальную задачу второго типа. Такое преобразование позволяет превратить любой алгоритм решения второй задачи в соответствующий алгоритм решения первой задачи.

Фундамент теории NP – полных задач был заложен в теореме С. Кука, опубликованной в 1971г. под названием “Сложность процедур вывода теорем”. В этой работе были заложены следующие основы этой теории:

1. Была определена важность понятия “сводимость за полиномиальное время”. Это понятие предполагает наличие алгоритма с полиномиальной временной сложностью преобразования задачи одного типа в задачу другого типа. Если первая задача полиноминально сводима ко второй задаче и для второй задачи имеется полиномиальный алгоритм её решения, то он может быть преобразован в полиномиальный алгоритм первой задачи.

2. Было обращено внимание на классы задач распознавания свойств, так называемый класс NP, которые могут быть решены за полиномиальное время на недетерминированном вычислительном устройстве:

N – недетерминированное устройство.

P – полиномиальное решение.

Большинство неподдающихся решению задач, встречающихся на практике, после переформулирования их в виде задач распознавания попадают в этот класс.

3. Кук доказал, что одна конкретная задача из класса NP называется задачей о выполнимости и обладает тем свойством, что любая задача из класса NP может быть сведена к ней за полиномиальное время. Таким образом, в некотором смысле, задачи выполнимости являются “самыми трудными” в классе NP.

4. В своей работе Кук предположил, что другие задачи из класса NP, аналогично задаче выполнимости, могут быть “самыми трудными” представителями класса NP, что и было им показано для ещё одной задачи из теории графов.

Позднее было показано, что имеется широкий круг задач, которые по своей трудности эквивалентны указанным двум задачам. Этот класс эквивалентных задач называется классом NP – полных задач (NPC).

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