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

Материал из WikiGrapp
Перейти к:навигация, поиск

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

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

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

См. также

Литература

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