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

Материал из WEGA

Метод сужения задачи (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], обычно настолько очевидно, что его даже не требуется указывать явно.

См. также

Литература

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