Метод локальной замены: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Метод локальной замены''' (''Local replacement method'') - один из трех общих методов док...)
 
Нет описания правки
Строка 1: Строка 1:
'''Метод локальной замены''' (''Local replacement method'') -  
'''Метод локальной замены''' (''[[Local replacement method]]'') -  
один из трех общих методов доказательства, которые часто
один из трех общих методов доказательства, которые часто
встречаются и могут подсказать путь к доказательству
встречаются и могут подсказать путь к доказательству
<math>\cal NP</math>-полноты новой задачи. Другие два --- это ''Метод
<math>\mathcal NP</math>-полноты новой задачи. Другие два --- это ''[[Метод сужения задачи]]'' и ''[[Метод построения компонент|Метод построения компоненты]]''.
сужения задачи'' и ''Метод построения компоненты''.


'''М.л.з.''' состоит в том, что выбирается некоторое
'''Метод локальной замены''' состоит в том, что выбирается некоторое
характерное свойство известной <math>{\cal NP}</math>-полной задачи, с
характерное свойство известной [[NP-полная задача|<math>{\mathcal NP}</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]

Версия от 11:51, 24 ноября 2009

Метод локальной замены (Local replacement method) - один из трех общих методов доказательства, которые часто встречаются и могут подсказать путь к доказательству [math]\displaystyle{ \mathcal NP }[/math]-полноты новой задачи. Другие два --- это Метод сужения задачи и Метод построения компоненты.

Метод локальной замены состоит в том, что выбирается некоторое характерное свойство известной [math]\displaystyle{ {\mathcal NP} }[/math]-полной задачи, с помощью него образуется семейство основных модулей, а соответствующие индивидуальные задачи заданной задачи получаются путем единообразной замены каждого основного модуля некоторой другой структурой.

Сводимости, возникающие при доказательстве методом локальной замены, достаточно нетривиальны, чтобы их всегда можно было с гарантией представить в стандартном виде, однако они остаются относительно несложными.

См. также

Задача о вершинном покрытии, Задача о выполнимости, Задача о клике, Задача о неэквивалентности регулярных выражений, Задача о разбиении, Задача о точном покрытии 3-множествами, Задача о трехмерном сочетании, Классы [math]\displaystyle{ \mathcal P }[/math] и [math]\displaystyle{ \mathcal NP }[/math], Полиномиальная сводимость (трансформируемость), [math]\displaystyle{ \mathcal NP }[/math]-Полная задача, Труднорешаемая задача.

Литература

[Гэри-Джонсон],

[Касьянов/95]