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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Метод локальной замены''' (''Local replacement method'') - один из трех общих методов док...)
 
Нет описания правки
 
(не показаны 2 промежуточные версии этого же участника)
Строка 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>-Полная задача]],''
* ''[[Труднорешаемая задача]].''
==Литература==
==Литература==
[Гэри-Джонсон],
* Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М.: Мир, 1982.


[Касьянов/95]
*Касьянов В.Н.  Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.

Текущая версия от 14:12, 11 мая 2011

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

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

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

См. также

Литература

  • Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М.: Мир, 1982.
  • Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.