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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Полиномиальная сводимость (трансформируемость)''' (''Polinomial transformation'') - Язык...)
 
Нет описания правки
Строка 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>.


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


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


(2) выбора подходящей известной <math>{\cal 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>;
Строка 15: Строка 12:
(4) доказательства того, что функция <math>f</math> осуществляет полиномиальное сведение.
(4) доказательства того, что функция <math>f</math> осуществляет полиномиальное сведение.


См. также Задача о вершинном покрытии, Задача о выполнимости, Задача о клике, Задача о  неэквивалентности регулярных выражений, Задача о разбиении, Задача о точном покрытии 3-множествами,
==См. также ==
Задача о трехмерном сочетании, Классы <math>\cal P</math> и <math>\cal NP</math>, Метод локальной замены, Метод построения компонент, Метод сужения задачи, <math>\cal NP</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]