Метод построения компонент

Метод построения компонент (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]-Полная задача,
• Труднорешаемая задача.

Литература

• Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М.: Мир, 1982.

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

Новосибирск: НГУ, 1995.