4624
правки
Glk (обсуждение | вклад) (Создана новая страница размером '''Метод локальной замены''' (''Local replacement method'') - один из трех общих методов док...) |
KEV (обсуждение | вклад) Нет описания правки |
||
(не показаны 2 промежуточные версии этого же участника) | |||
Строка 1: | Строка 1: | ||
'''Метод локальной замены''' (''Local replacement method'') | '''Метод локальной замены''' (''[[Local replacement method]]'') — | ||
один из трех общих методов доказательства, которые часто | один из трех общих методов доказательства, которые часто | ||
встречаются и могут подсказать путь к доказательству | встречаются и могут подсказать путь к доказательству | ||
<math>\ | <math>\mathcal NP</math>-полноты новой задачи. Другие два — это ''[[Метод сужения задачи]]'' и ''[[Метод построения компонент|Метод построения компоненты]]''. | ||
сужения задачи'' и ''Метод построения компоненты''. | |||
''' | '''Метод локальной замены''' состоит в том, что выбирается некоторое | ||
характерное свойство известной <math>{\ | характерное свойство известной [[NP-Полная задача|<math>{\mathcal NP}</math>-полной задачи]], с | ||
помощью него образуется семейство основных модулей, а | помощью него образуется семейство основных модулей, а соответствующие индивидуальные задачи заданной задачи получаются путем единообразной замены каждого основного модуля некоторой другой структурой. | ||
соответствующие индивидуальные задачи заданной задачи | |||
получаются путем единообразной замены каждого основного | |||
модуля некоторой другой структурой. | |||
Сводимости, возникающие при доказательстве ''методом | Сводимости, возникающие при доказательстве ''методом локальной замены'', достаточно нетривиальны, чтобы их всегда можно было с гарантией представить в стандартном виде, | ||
локальной замены'', достаточно нетривиальны, чтобы их всегда | |||
можно было с гарантией представить в стандартном виде, | |||
однако они остаются относительно несложными. | однако они остаются относительно несложными. | ||
См. также ''Задача о вершинном покрытии, Задача о выполнимости, Задача о клике, Задача о неэквивалентности регулярных выражений, Задача о разбиении, Задача о точном покрытии 3-множествами, Задача о трехмерном сочетании, Классы <math>\ | ==См. также== | ||
* ''[[Задача о вершинном покрытии]],'' | |||
* ''[[Задача о выполнимости]],'' | |||
* ''[[Задача о клике]],'' | |||
* ''[[Задача о неэквивалентности регулярных выражений]],'' | |||
* ''[[Задача о разбиении]],'' | |||
* ''[[Задача о точном покрытии 3-множествами]],'' | |||
* ''[[Задача о трехмерном сочетании]],'' | |||
* ''[[Классы P и NP|Классы <math>\mathcal P</math> и <math>\mathcal NP</math>]],'' | |||
* ''[[Полиномиальная сводимость (трансформируемость)]],'' | |||
* ''[[NP-Полная задача|<math>\mathcal NP</math>-Полная задача]],'' | |||
* ''[[Труднорешаемая задача]].'' | |||
==Литература== | ==Литература== | ||
* Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М.: Мир, 1982. | |||
*Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995. |