4624
правки
Glk (обсуждение | вклад) (Создана новая страница размером '''Полиномиальная сводимость (трансформируемость)''' (''Polinomial transformation'') - Язык...) |
KEV (обсуждение | вклад) Нет описания правки |
||
(не показана 1 промежуточная версия этого же участника) | |||
Строка 1: | Строка 1: | ||
'''Полиномиальная сводимость (трансформируемость)''' (''Polinomial transformation'') | '''Полиномиальная сводимость (трансформируемость)''' (''[[Polinomial transformation]]'') — | ||
Язык <math>L</math> называется ''полиномиально сводимым (трансформируемым)'' к <math>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> | ||
часть ее ленты), что <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> | |||
(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> | (3) построения функции <math>\,f,</math> сводящей задачу <math>\,P'</math> к задаче <math>\,P;</math> | ||
(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>-полная задача]],'' | |||
* ''[[Труднорешаемая задача]].'' | |||
==Литература== | ==Литература== | ||
* Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979. | |||
* Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995. |