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

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


(2) выбора подходящей известной <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>;
(3) построения функции <math>\,f,</math> сводящей задачу <math>\,P'</math> к задаче <math>\,P;</math>


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


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


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

Текущая версия от 13:38, 8 июня 2011

Полиномиальная сводимость (трансформируемость) (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] осуществляет полиномиальное сведение.

См. также

Литература

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