Полиномиальная сводимость

Рассмотрим класс задач NP. Здесь можно говорить о сводимости языков. Формальное определения полиномиальной сводимости следующее.

Определение. Говорят, что язык L₁ÍA* сводится к языку L₂ÍB*, если существует такое отображение f: A*®B*, что выполняются два условия.

1. Функция f вычисляется за полиномиальное время. (Например, существует МТ, которая за полиномиальное число тактов вычисляет эту функцию.)

2. Для любого входа IÎA* соотношение IÎL₁ выполняется тогда и только тогда, когда выполняется соотношение f(I)ÎL₂.

Сводимость языков обозначается L₁µL₂.

Вначале приведем два простых примера.

Пример. Задача "гамильтонов цикл" сводится к задаче "коммивояжер".

Схема решения. Матрица весов ребер A задачи коммивояжер строится из матрицы инциденций графа G задачи гамильтонов цикл по правилам: наличие ребра в G соответствует единице в A, а его отсутствие соответствует двойке. Число B для задачи коммивояжер определяется равным числу вершин в G.

Определим задачу «3-КНФ» как частный случай задачи «КНФ-выпонимость», в котором каждая КНФ содержит не более трех литералов.

Теперь приведем два очевидных свойства соотношения "сводимость".

Лемма. Если L₁µL₂ и L₂ÎP, то L₂ÎP.

Доказательство. Смысл этого утверждения в том, что сведения некоторой новой задачи к известной полиномиально разрешимой позволяет утверждать, что эта новая также полиномиально разрешима.

Мы приводим доказательство этого утверждения, так как оно конструктивно и, по сути дела, описывает алгоритм решения новой задачи.

Пусть A и B алфавиты языков L₁ и L₂, а функция f: A*®B* осуществляет полиномиальную сводимость L₁ к L₂.

Так как L₂ÎP, то существует МТ, которая за полиномиальное число тактов решает эту задачу. Обозначим эту машину через М₂. Через М_f обозначим машину Тьюринга, которая за полиномиальное число тактов вычисляет эту функцию f. Верхние оценки сложности решения обозначим через p₂(n) и p_f(n), где p₂ и p_f - некоторые полиномы.

Построим теперь МТ, которая решает первую задачу (допускает язык L₁). Пусть задан некоторый вход IÎL₁ (условие индивидуальной задачи). Сначала с помощью М_f преобразуем его во вход f(I) второй задачи. Затем с помощью М₂ выясняем справедливость соотношения f(I)ÎL₂. Так как для любого входа IÎA* соотношение IÎL₁ выполняется тогда и только тогда, когда выполняется соотношение f(I)ÎL₂, то требуемый алгоритм построен. Время работы ограничено O(p₂(p_f(I)) + p_f(I))), что является полиномом, от n.

Лемма доказана.

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

Соотношение полиномиальной сводимости транзитивно, то есть справедливо следующее соотношение.

Лемма. Если L₁µL₂ и L₂µL₃, то L₁µL₃.

Доказательство этого утверждения очевидно.

Дата добавления: 2015-07-11