Задача о выполнимости

Материал из WikiGrapp
Перейти к:навигация, поиск

Задача о выполнимости (Satisfiability problem) — одна из основных \mathcal NP-полных задач. Формулируется следующим образом.

У с л о в и е. Задано множество булевых переменных V и правильно построенное булево выражение E над V.

В о п р о с. Существует ли набор значений переменных множества V, при котором выражение E выполнено, т.е. принимает значение "истина"?

Можно показать, что даже при более жестких ограничениях на вид формулы задача выполнимости булевых формул также {\mathcal NP}-полна.

Булева формула находится в конъюнктивной нормальной форме (КНФ), если она представляет собой произведение сумм литералов, где каждый литерал имеет вид x или \lnot x для некоторой переменной x. Задача выполнимости формул, находящихся в КНФ, {\mathcal NP}-полна.

Говорят, что булева формула находится в k-конъюнктивной нормальной форме (k-КНФ), если она представляет собой произведение сумм, состоящих не более чем из k литералов. Задача k-выполнимости (k-ВЫП) состоит в выяснении выполнимости формулы, находящейся в k-КНФ.

Для k=1 и 2 известны полиномиальные алгоритмы, проверяющие k-выполнимость, т.е. 1-ВЫП, 2-ВЫП \in \mathcal NP. Ситуация изменяется при k=3, поскольку задача о 3-выполнимости является {\mathcal NP}- полной.


См. также

Литература

  • Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979.
  • Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.