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

Метод локальной замены (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]-Полная задача,
• Труднорешаемая задача.

Литература

• Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М.: Мир, 1982.

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