Метод построения компонент: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Метод построения компонент''' (''Component design method'') - один из трех общих методов...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Метод построения компонент''' (''Component design method'') - | '''Метод построения компонент''' (''[[Component design method]]'') - | ||
один из трех общих методов доказательства, которые часто | один из трех общих методов доказательства, которые часто | ||
встречаются и могут подсказать путь к доказательству <math>{\ | встречаются и могут подсказать путь к доказательству <math>{\mathcal | ||
NP}</math>-полноты новой задачи. Другие два --- это | NP}</math>-полноты новой задачи. Другие два --- это | ||
''метод локальной замены'' и ''метод сужения задачи''. | ''[[метод локальной замены]]'' и ''[[метод сужения задачи]]''. | ||
Является наиболее сложным из упомянутых выше методов | Является наиболее сложным из упомянутых выше методов | ||
доказательства <math>{\ | доказательства <math>{\mathcal NP}</math>-полноты. | ||
Основная идея таких доказательств заключается в том, чтобы с | Основная идея таких доказательств заключается в том, чтобы с | ||
помощью составных частей рассматриваемой задачи | помощью составных частей рассматриваемой задачи | ||
сконструировать некоторые "компоненты", соединяя которые | сконструировать некоторые "компоненты", соединяя которые | ||
можно "реализовать" индивидуальные задачи известной <math>{\ | можно "реализовать" индивидуальные задачи известной <math>{\mathcal | ||
NP}</math>-полной задачи. При этом можно выделить компоненты двух | NP}</math>-полной задачи. При этом можно выделить компоненты двух | ||
основных типов. Одни из них можно рассматривать как | основных типов. Одни из них можно рассматривать как | ||
компоненты, "делающие выбор" (например, выбирающие вершины, | компоненты, "делающие выбор" (например, выбирающие [[вершина|вершины]], | ||
выбирающие значения истинности переменных), а другие --- как | выбирающие значения истинности переменных), а другие --- как | ||
компоненты, "проверяющие свойства" (например, проверяющие, | компоненты, "проверяющие свойства" (например, проверяющие, | ||
что каждое ребро покрыто или что каждая дизъюнкция | что каждое [[ребро]] покрыто или что каждая дизъюнкция | ||
выполнена). | выполнена). | ||
| Строка 25: | Строка 25: | ||
Вообще говоря, любое доказательство можно считать основанным на | Вообще говоря, любое доказательство можно считать основанным на | ||
''' | '''методе построения компонент''', если конструируемая в нем | ||
индивидуальная задача представляет собой набор компонент, каждая | индивидуальная задача представляет собой набор компонент, каждая | ||
из которых выполняет определенные функции, формулируемые в | из которых выполняет определенные функции, формулируемые в | ||
терминах исходной задачи. Общая сводимость, использованная при | терминах исходной задачи. Общая сводимость, использованная при | ||
доказательстве теоремы Кука о выполнимости булевых формул, | доказательстве [[теорема Кука|теоремы Кука]] о выполнимости булевых формул, | ||
является хорошим примером доказательств такого типа. | является хорошим примером доказательств такого типа. | ||
См. также ''Задача о вершинном покрытии, Задача о выполнимости, Задача о клике, Задача о неэквивалентности регулярных выражений, Задача о разбиении, Задача о точном покрытии 3-множествами, Задача о трехмерном сочетании, Классы <math>\ | ==См. также== | ||
''[[Задача о вершинном покрытии]], [[Задача о выполнимости]], [[Задача о клике]], [[Задача о неэквивалентности регулярных выражений]], [[Задача о разбиении]], [[Задача о точном покрытии 3-множествами]], [[Задача о трехмерном сочетании]], [[Классы P и NP|Классы <math>\mathcal P</math> и <math>\mathcal NP</math>]], [[Полиномиальная сводимость (трансформируемость)]], [[NP-Полная задача|<math>\mathcal NP</math>-Полная задача]], [[Труднорешаемая задача]].'' | |||
==Литература== | ==Литература== | ||
[Гэри-Джонсон], | [Гэри-Джонсон], | ||
[Касьянов/95] | [Касьянов/95] | ||
Версия от 11:57, 24 ноября 2009
Метод построения компонент (Component design method) - один из трех общих методов доказательства, которые часто встречаются и могут подсказать путь к доказательству [math]\displaystyle{ {\mathcal NP} }[/math]-полноты новой задачи. Другие два --- это метод локальной замены и метод сужения задачи. Является наиболее сложным из упомянутых выше методов доказательства [math]\displaystyle{ {\mathcal NP} }[/math]-полноты.
Основная идея таких доказательств заключается в том, чтобы с помощью составных частей рассматриваемой задачи сконструировать некоторые "компоненты", соединяя которые можно "реализовать" индивидуальные задачи известной [math]\displaystyle{ {\mathcal NP} }[/math]-полной задачи. При этом можно выделить компоненты двух основных типов. Одни из них можно рассматривать как компоненты, "делающие выбор" (например, выбирающие вершины, выбирающие значения истинности переменных), а другие --- как компоненты, "проверяющие свойства" (например, проверяющие, что каждое ребро покрыто или что каждая дизъюнкция выполнена).
В рассматриваемой индивидуальной задаче эти компоненты связаны так, что выбранные значения передаются компонентам, проверяющим условия, и последние проверяют, удовлетворяют ли сделанные выборы значений необходимым условиям.
Вообще говоря, любое доказательство можно считать основанным на методе построения компонент, если конструируемая в нем индивидуальная задача представляет собой набор компонент, каждая из которых выполняет определенные функции, формулируемые в терминах исходной задачи. Общая сводимость, использованная при доказательстве теоремы Кука о выполнимости булевых формул, является хорошим примером доказательств такого типа.
См. также
Задача о вершинном покрытии, Задача о выполнимости, Задача о клике, Задача о неэквивалентности регулярных выражений, Задача о разбиении, Задача о точном покрытии 3-множествами, Задача о трехмерном сочетании, Классы [math]\displaystyle{ \mathcal P }[/math] и [math]\displaystyle{ \mathcal NP }[/math], Полиномиальная сводимость (трансформируемость), [math]\displaystyle{ \mathcal NP }[/math]-Полная задача, Труднорешаемая задача.
Литература
[Гэри-Джонсон],
[Касьянов/95]