Метод сужения задачи

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

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

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

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

Литература

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

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