4624
правки
Glk (обсуждение | вклад) (Создана новая страница размером '''Метод локальной замены''' (''Local replacement method'') - один из трех общих методов док...) |
KEV (обсуждение | вклад) Нет описания правки |
||
Строка 1: | Строка 1: | ||
'''Метод локальной замены''' (''Local replacement method'') - | '''Метод локальной замены''' (''[[Local replacement method]]'') - | ||
один из трех общих методов доказательства, которые часто | один из трех общих методов доказательства, которые часто | ||
встречаются и могут подсказать путь к доказательству | встречаются и могут подсказать путь к доказательству | ||
<math>\ | <math>\mathcal NP</math>-полноты новой задачи. Другие два --- это ''[[Метод сужения задачи]]'' и ''[[Метод построения компонент|Метод построения компоненты]]''. | ||
сужения задачи'' и ''Метод построения компоненты''. | |||
''' | '''Метод локальной замены''' состоит в том, что выбирается некоторое | ||
характерное свойство известной <math>{\ | характерное свойство известной [[NP-полная задача|<math>{\mathcal NP}</math>-полной задачи]], с | ||
помощью него образуется семейство основных модулей, а | помощью него образуется семейство основных модулей, а соответствующие индивидуальные задачи заданной задачи получаются путем единообразной замены каждого основного модуля некоторой другой структурой. | ||
соответствующие индивидуальные задачи заданной задачи | |||
получаются путем единообразной замены каждого основного | |||
модуля некоторой другой структурой. | |||
Сводимости, возникающие при доказательстве ''методом | Сводимости, возникающие при доказательстве ''методом локальной замены'', достаточно нетривиальны, чтобы их всегда можно было с гарантией представить в стандартном виде, | ||
локальной замены'', достаточно нетривиальны, чтобы их всегда | |||
можно было с гарантией представить в стандартном виде, | |||
однако они остаются относительно несложными. | однако они остаются относительно несложными. | ||
См. также ''Задача о вершинном покрытии, Задача о выполнимости, Задача о клике, Задача о неэквивалентности регулярных выражений, Задача о разбиении, Задача о точном покрытии 3-множествами, Задача о трехмерном сочетании, Классы <math>\ | ==См. также== | ||
''[[Задача о вершинном покрытии]], [[Задача о выполнимости]], [[Задача о клике]], [[Задача о неэквивалентности регулярных выражений]], [[Задача о разбиении]], [[Задача о точном покрытии 3-множествами]], [[Задача о трехмерном сочетании]], [[Классы P и NP|Классы <math>\mathcal P</math> и <math>\mathcal NP</math>]], [[Полиномиальная сводимость (трансформируемость)]], [[NP-Полная задача|<math>\mathcal NP</math>-Полная задача]], [[Труднорешаемая задача]].'' | |||
==Литература== | ==Литература== | ||
[Гэри-Джонсон], | [Гэри-Джонсон], | ||
[Касьянов/95] | [Касьянов/95] |