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

'''Задача о выполнимости''' (''Satisfiability problem'') -  

одна из основных ''<math>\cal NP</math>-полных'' задач.

Формулируется следующим образом.

У с л о в и е. Задано множество булевых переменных <math>V</math> и

правильно построенное булево выражение <math>E</math> над <math>V</math>.

В о п р о с. Существует ли набор значений переменных

множества <math>V</math>, при котором выражение <math>E</math> выполнено, т.е.

принимает значение "истина"?

Можно показать, что даже при более жестких ограничениях на

вид формулы задача выполнимости булевых формул также <math>{\cal

NP}</math>-полна.

Булева формула находится в ''конъюнктивной нормальной

форме''\linebreak (КНФ), если она представляет собой произведение сумм

литералов, где каждый ''литерал'' имеет вид <math>x</math> или <math>\lnot

x</math> для некоторой переменной <math>x</math>.

Задача выполнимости формул, находящихся в КНФ, <math>{\cal

NP}</math>-полна.

Говорят, что булева формула находится в <math>k</math>-''конъюнктивной нормальной форме'' (<math>k</math>-КНФ), если она

представляет собой произведение сумм, состоящих не более чем

состоит в выяснении выполнимости формулы, находящейся в

<math>k</math>-КНФ.

Для <math>k=1</math> и 2 известны ''полиномиальные алгоритмы'',

проверяющие <math>k</math>-выполнимость, т.е. ''1-ВЫП, 2-ВЫП'' <math>\in \cal NP</math>.

Ситуация изменяется при <math>k=3</math>, поскольку задача о

3-выполнимости является <math>{\cal NP}</math>- полной.

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