Лекция 4 np – полные задачи

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

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

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

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

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

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

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

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

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

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

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

Задачи распознавания

Из соображения удобства теория NP – полных задач строится только для задач распознавания свойств. Такие задачи имеют только два возможных решения: “да” и “нет”. Формально, задачи распознавания П состоят из двух множеств: 1) множество D_Пвсех возможных индивидуальных задач; 2) Множествоиндивидуальных задач с ответом “да”. Стандартная форма, которую мы будем применять для описания задач, состоит из двух частей: в первой части даётся описание условия задачи в терминах различных компонентов, во второй части формулируется вопрос-предположение, предполагающий один из двух ответов: “да” или “нет”. Это описание определяет множестваD_ПиY_П. Задача принадлежит множествуD_Пв том случае, когда она может быть получена из стандартной формы описания задачи П подстановкой конкретных значений во все компоненты условий индивидуальных задач, множествуY_Пв том случае, когда ответом на вопрос задачи будет “да”.