Полиномиальная сводимость (трансформируемость): различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Полиномиальная сводимость (трансформируемость)''' (''Polinomial transformation'') - Язык...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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>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>\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>-полноты других задач (языков) может быть существенно упрощена. Для доказательства <math>{\ | |||
<math>P</math>. Таким образом, процесс доказательства <math>{\ | |||
(1) доказательства, что <math>P \in {\ | (1) доказательства, что <math>P \in {\mathcal NP}</math>; | ||
(2) выбора подходящей известной <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>; | ||
| Строка 15: | Строка 12: | ||
(4) доказательства того, что функция <math>f</math> осуществляет полиномиальное сведение. | (4) доказательства того, что функция <math>f</math> осуществляет полиномиальное сведение. | ||
См. также Задача о вершинном покрытии, Задача о выполнимости, Задача о клике, Задача о неэквивалентности регулярных выражений, Задача о разбиении, Задача о точном покрытии 3-множествами, | ==См. также == | ||
Задача о трехмерном сочетании, Классы <math>\ | ''[[Задача о вершинном покрытии]], [[Задача о выполнимости]], [[Задача о клике]], [[Задача о неэквивалентности регулярных выражений]], [[Задача о разбиении]], [[Задача о точном покрытии 3-множествами]], [[Задача о трехмерном сочетании]], [[Классы P и NP|Классы <math>\mathcal P</math> и <math>\mathcal NP</math>]], [[Метод локальной замены]], [[Метод построения компонент]], [[Метод сужения задачи]], [[NP-Полная задача|<math>\mathcal NP</math>-полная задача]], [[Труднорешаемая задача]].'' | ||
Труднорешаемая задача. | |||
==Литература== | ==Литература== | ||
[Ахо-Хопкрофт-Ульман], | [Ахо-Хопкрофт-Ульман], | ||
[Касьянов/95] | [Касьянов/95] | ||
Версия от 12:15, 21 декабря 2009
Полиномиальная сводимость (трансформируемость) (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].
Отношение полиномиальной сводимости обладает свойством транзитивности. Поэтому, если уже известна [[NP-Полная задача|[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]-полная задача, Труднорешаемая задача.
Литература
[Ахо-Хопкрофт-Ульман],
[Касьянов/95]