4.3 Примеры задач np-класса.

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

Пусть х₁, х₂, …, х_n – множество логических переменных; – их отрицания или дополнения.

if x_i = true then = false

 - И;  - ИЛИ.

Дизъюнкция: х₁  х₅  …

Конъюнкция: х₄  х₃  …

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

E^*(x₁, …, x_n) = (x₁  x₂  x₃)  (x₁   )  (  x₄)  ( ) (*)

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

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

А(ВС)=( АВ)(АС)

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

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

(*)

Например:

Функция

f₂(x_i)=(x₁  x₂)( )( )

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

Теорема:

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

for i=1 to N do

x_i  выбор (true, false)

if E(x₁, x₂, …, x_N) then успех

else неудача

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

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

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

Минимальный случай К=3. Для булевской функции, представленной в КНФ, за полиномиальное время можно найти функцию Е^*(х₂), содержащую не более трех переменных в каждом дизъюнкте. Тогда Е выполнима, если выполнима Е^*.

E^*(x₁, x₂,…, x_n)E^*(x_i)

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

(₁  ₂ … _k)=(₁  ₂  z)  (₃  ₄ … _k  )

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

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

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

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

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

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

3. Определение вершинного покрытия мощности L для неориентированного графа (NP-полная задача).

4. Определение максимума вершинных покрытий неориентированного графа (NP-трудная задача).

5. Задача определения существования Гамильтонова цикла для графа (NP-полная задача).

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

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