Метод локальной замены

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

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

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

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

Литература

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

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