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

Перейти к навигации Перейти к поиску
нет описания правки
(Создана новая страница размером '''Полиномиальная сводимость (трансформируемость)''' (''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]

Навигация