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

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

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

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

См. также

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

Литература

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

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