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

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

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

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

См. также

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

Литература

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

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