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

Пусть х1, х2, …, хn – множество логических переменных; x, x,..., xn 1 2 – их

отрицания или дополнения.

if xi = true then i x = false

Ú - И; Ù - ИЛИ.

Дизъюнкция: х1 Ú х5 Ú x 2 Ú …

Конъюнкция: х4 Ù х3 Ù x 2 Ù …

Конъюнктивная нормальная форма:

E*(x1, …, xn) = (x1 Ú x2 Ú x3) Ù (x1 Ú x 2 Ú x 4 ) Ù ( 3 x Ú x4) Ù (x 1 ) (*)

Задача о выполнимости заключается в определении, является ли

булевская функция, записанная в КНФ, выполнимой.

Любая булевская функция может быть представлена в КНФ по правилу

Де Моргана:

ï î

ï í ì

Ç = È

È = Ç

A B A B

A B A B

А Ú (В Ù С)=(А Ú В) Ù (А Ú С)

Говорят, что булевская функция выполнима, если существует некоторое

присваивание переменным true или false, при этом функция должна быть

равна true.

Для функции (*) она будет выполнима, если ввести следующие

присваивания:

(*)

î í ì

=

= = =

x true

x x x false

1 2 4

Например:

Функция

f2(xi)=(x1 Ú x2) Ù (x 1 ) Ù (x 2 )

не является выполнимой, т. к. при любых xi f2(xi)=false.

Теорема:

Задача о выполнимости является NP-полной.

for i=1 to N do

xi выбор (true, false)

if E(x1, x2, …, xN) then успех

else неудача

Используя преобразование задачи Р1 в Р2, можно показать, что даже

ограниченный случай задачи о выполнимости является NP-полным.

К-выполнимость.

К-выполнимость означает, что любой дизъюнкт, входящий в КНФ,

содержит не более К логических переменных.

Минимальный случай К=3. Для булевской функции, представленной в

КНФ, за полиномиальное время можно найти функцию Е*(х2), содержащую не

более трех переменных в каждом дизъюнкте. Тогда Е выполнима, если

выполнима Е*.

E*(x1, x2, …, xn) ® E*(xi)

Для этого используется метод уменьшения порядка дизъюнкта

( a 1 Ú a 2 Ú … Ú a k)=( a 1 Ú a 2 Ú z) Ù ( a 3 Ú a 4 Ú … Ú a k Ú z)

Применяя итерационный процесс разложения, можно получить Е*.

Найти алгоритм решения Е* проще, чем функции Е. Но при этом доказав

выполнимость Е*, докажем выполнимость исходной функции Е.

Частный случай: при К=2 функция Е входит в Р.

Примерами задач NP-класса могут послужить также задачи на графах:

1) Определение максимума клик неориентированного графа (NP-

трудная задача).

2) Задача определения полного подграфа (NP-полная задача).

3) Определение вершинного покрытия мощности L для

неориентированного графа (NP-полная задача).

4) Определение максимума вершинных покрытий

неориентированного графа (NP-трудная задача).

5) Задача определения существования Гамильтонова цикла для

графа (NP-полная задача).

6) Задача коммивояжера: определение оптимального движения по

графу с единым вхождением в каждую вершину (NP-трудная задача).

Задача составления расписания (NP-полная задача).