Метод построения компонент: различия между версиями

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


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


Строка 25: Строка 25:


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


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


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

Текущая версия от 14:17, 11 мая 2011

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

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

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

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

См. также

Литература

  • Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М.: Мир, 1982.
  • Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. —

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