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

'''Полиномиальная сводимость (трансформируемость)''' (''[[Polinomial transformation]]'') -  

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

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

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

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

==См. также ==

''[[Задача о вершинном покрытии]], [[Задача о выполнимости]], [[Задача о клике]], [[Задача о  неэквивалентности регулярных выражений]], [[Задача о разбиении]], [[Задача о точном покрытии 3-множествами]], [[Задача о трехмерном сочетании]], [[Классы P и NP|Классы <math>\mathcal P</math> и <math>\mathcal NP</math>]], [[Метод локальной замены]], [[Метод построения компонент]], [[Метод сужения задачи]], [[NP-Полная задача|<math>\mathcal NP</math>-полная задача]], [[Труднорешаемая задача]].''