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

'''Метод локальной замены''' (''Local replacement method'') -  

<math>\cal NP</math>-полноты новой задачи. Другие два --- это ''Метод

сужения задачи'' и ''Метод построения компоненты''.

'''М.л.з.''' состоит в том, что выбирается некоторое

характерное свойство известной <math>{\cal NP}</math>-полной задачи, с

помощью него образуется семейство основных модулей, а

соответствующие индивидуальные задачи заданной задачи

получаются путем единообразной замены каждого основного

модуля некоторой другой структурой.

Сводимости, возникающие при доказательстве ''методом

локальной замены'', достаточно нетривиальны, чтобы их всегда

можно было с гарантией представить в стандартном виде,

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