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

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

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

(2) выбора подходящей известной [math]\displaystyle{ {\mathcal 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{ \mathcal P }[/math] и [math]\displaystyle{ \mathcal NP }[/math],
• Метод локальной замены,
• Метод построения компонент,
• Метод сужения задачи,
• [math]\displaystyle{ \mathcal NP }[/math]-полная задача,
• Труднорешаемая задача.

Литература

• Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979.

• Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.