Просмотр кода страницы Метод построения компонент

'''Метод построения компонент''' (''[[Component design method]]'') - 
один из трех общих методов доказательства, которые часто
встречаются и могут подсказать путь к доказательству <math>{\mathcal
NP}</math>-полноты новой задачи. Другие два --- это
''[[метод локальной замены]]'' и ''[[метод сужения задачи]]''.
Является наиболее сложным из упомянутых выше методов
доказательства <math>{\mathcal NP}</math>-полноты.

Основная идея таких доказательств заключается в том, чтобы с
помощью составных частей рассматриваемой задачи
сконструировать некоторые "компоненты", соединяя которые
можно "реализовать" индивидуальные задачи известной <math>{\mathcal
NP}</math>-полной задачи. При этом можно выделить компоненты двух
основных типов. Одни из них можно рассматривать как
компоненты, "делающие выбор" (например, выбирающие [[вершина|вершины]],
выбирающие значения истинности переменных), а другие --- как
компоненты, "проверяющие свойства" (например, проверяющие,
что каждое [[ребро]] покрыто или что каждая дизъюнкция
выполнена).

В рассматриваемой индивидуальной задаче эти компоненты связаны так,
что выбранные значения передаются компонентам, проверяющим условия, и
последние проверяют, удовлетворяют ли сделанные выборы значений
необходимым условиям.

Вообще говоря, любое доказательство можно считать основанным на
'''методе построения компонент''', если конструируемая в нем
индивидуальная задача представляет собой набор компонент, каждая
из которых выполняет определенные функции, формулируемые в
терминах исходной задачи. Общая сводимость, использованная при
доказательстве [[теорема Кука|теоремы Кука]] о выполнимости булевых формул,
является хорошим примером доказательств такого типа.

==См. также== 
''[[Задача о вершинном покрытии]], [[Задача о выполнимости]], [[Задача о клике]], [[Задача о неэквивалентности регулярных выражений]], [[Задача о разбиении]], [[Задача о точном покрытии 3-множествами]], [[Задача о трехмерном сочетании]], [[Классы P и NP|Классы <math>\mathcal P</math> и <math>\mathcal NP</math>]], [[Полиномиальная сводимость (трансформируемость)]], [[NP-Полная задача|<math>\mathcal NP</math>-Полная задача]], [[Труднорешаемая задача]].''
==Литература==
[Гэри-Джонсон],

[Касьянов/95]