Основные понятия и определения дисциплины

К-выполнимость.
К-выполнимость означает, что любой дизъюнкт, входящий в КНФ, содержит не более К логических переменных.Минимальный случай К=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-полная задача).
   

23.