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

'''Метод сужения задачи''' (''Restriction method'') -

встречаются и могут подсказать путь к доказательству <math>{\cal

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

''Метод локальной замены'' и ''Метод построения

компонент''.

Доказательство ''методом сужения'' <math>{\cal NP}</math>-полноты

фиксированной задачи <math>Q\in {\cal NP}</math> заключается

просто-напросто в установлении того, что задача <math>Q</math> включает

в качестве частного случая известную <math>{\cal NP}</math>-полную

задачу <math>Q'</math>.

задачи из <math>Q</math>, чтобы получившаяся в результате сужения

задача была бы эквивалентна <math>Q'</math>. При этом не требуется,

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

сведение <math>Q'</math> к <math>Q</math>, обычно настолько очевидно, что его даже

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

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

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