Полиномиальная сводимость (трансформируемость)

Полиномиальная сводимость (трансформируемость) (Polinomial transformation) - Язык [math]\displaystyle{ L }[/math] называется полиномиально сводимым (трансформируемым) к [math]\displaystyle{ L_0 }[/math], если некоторая машина Тьюринга с полиномиальной временной сложностью [math]\displaystyle{ M }[/math] преобразует каждую цепочку [math]\displaystyle{ \omega }[/math] в алфавите языка [math]\displaystyle{ L }[/math] в такую цепочку [math]\displaystyle{ \omega_0 }[/math] в алфавите языка [math]\displaystyle{ L_0 }[/math] (т.е. [math]\displaystyle{ M }[/math], обрабатывая цепочку [math]\displaystyle{ \omega }[/math], достигает заключительной конфигурации, в которой [math]\displaystyle{ \omega_0 }[/math] --- непустая часть ее ленты), что [math]\displaystyle{ \omega\in L }[/math] тогда и только тогда, когда [math]\displaystyle{ \omega_0\in L_0 }[/math].

Отношение П.с. обладает свойством транзитивности. Поэтому, если уже известна [math]\displaystyle{ {{\cal NP'' }[/math]-полнота} одной из задач (одного из языков), то процедура доказательства [math]\displaystyle{ {\cal NP} }[/math]-полноты других задач (языков) может быть существенно упрощена. Для доказательства [math]\displaystyle{ {\cal NP} }[/math]-полноты задачи [math]\displaystyle{ P \in {\cal NP} }[/math] достаточно показать, что какая-нибудь из известных [math]\displaystyle{ {\cal NP} }[/math]-полных задач [math]\displaystyle{ P' }[/math] может быть сведена к [math]\displaystyle{ P }[/math]. Таким образом, процесс доказательства [math]\displaystyle{ {\cal NP} }[/math]-полноты задачи [math]\displaystyle{ P }[/math] может состоять из следующих четырех шагов:

(1) доказательства, что [math]\displaystyle{ P \in {\cal NP} }[/math];

(2) выбора подходящей известной [math]\displaystyle{ {\cal NP} }[/math]-полной задачи [math]\displaystyle{ P' }[/math];

(3) построения функции [math]\displaystyle{ f }[/math], сводящей задачу [math]\displaystyle{ P' }[/math] к задаче [math]\displaystyle{ P }[/math];

(4) доказательства того, что функция [math]\displaystyle{ f }[/math] осуществляет полиномиальное сведение.

См. также Задача о вершинном покрытии, Задача о выполнимости, Задача о клике, Задача о неэквивалентности регулярных выражений, Задача о разбиении, Задача о точном покрытии 3-множествами, Задача о трехмерном сочетании, Классы [math]\displaystyle{ \cal P }[/math] и [math]\displaystyle{ \cal NP }[/math], Метод локальной замены, Метод построения компонент, Метод сужения задачи, [math]\displaystyle{ \cal NP }[/math]-полная задача, Труднорешаемая задача.

Литература

[Ахо-Хопкрофт-Ульман],

[Касьянов/95]