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

'''Полиномиальная сводимость (трансформируемость)''' (''[[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> может состоять из следующих четырех шагов:

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

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

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

* ''[[Задача о вершинном покрытии]],''

* ''[[Задача о выполнимости]],''

* ''[[Задача о клике]],''

* ''[[Задача о  неэквивалентности регулярных выражений]],''

* ''[[Задача о разбиении]],''

* ''[[Задача о точном покрытии 3-множествами]],''

* ''[[Задача о трехмерном сочетании]],''

* ''[[Классы P и NP|Классы <math>\mathcal P</math> и <math>\mathcal NP</math>]],''

* ''[[Метод локальной замены]],''

* ''[[Метод построения компонент]],''

* ''[[Метод сужения задачи]],''

* ''[[NP-Полная задача|<math>\mathcal NP</math>-полная задача]],''

* ''[[Труднорешаемая задача]].''

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

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