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

'''Метод построения компонент''' (''[[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>-Полная задача]],''
* ''[[Труднорешаемая задача]].''
==Литература==
* Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М.: Мир, 1982.

* Касьянов В.Н.  Лекции по теории формальных языков, автоматов и сложности вычислений.  —
Новосибирск: НГУ, 1995.