|
K - amalga oshirish imkoniyati .
K-qoniqarliligi CNFga kiritilgan har qanday bandda ko'pi bilan K mantiqiy o'zgaruvchilar mavjudligini anglatadi.
Minimal holat K = 3. CNFda ifodalangan mantiqiy funktsiya uchun polinom vaqtida funktsiyani topish mumkin E * (x2) har bir bandda ko'pi bilan uchta o'zgaruvchini o'z ichiga oladi. Keyin E amalga oshirish mumkin bo'lsa E *.
E* (x1 , x2 ,…, xn) ® E* (xi)
Buning uchun band tartibini kamaytirish usuli qo'llaniladi
(a1 Ú a2 Ú … Ú ak)=(a1 Ú a2 Ú z) Ù (a3 Ú a4 Ú … Ú ak Ú )
Iterativ parchalanish jarayonini qo'llash orqali olish mumkin E *.
Yechim algoritmini toping E * funksiyalarga qaraganda oddiyroq E... Ammo shu bilan birga, maqsadga muvofiqligini isbotladi E *, biz asl funktsiyaning qoniqarliligini isbotlaymiz E.
Maxsus holat: K = 2 uchun funktsiya E R ga kiritilgan.
NP-sinf muammolariga misollar ham grafik muammolar :
1) Yo'naltirilmagan grafikning kliklarining maksimalini aniqlash (NP-qiyin masala).
2) To'liq subgrafani aniqlash masalasi (NP-to'liq muammo).
3) Yo'naltirilmagan grafik uchun L kardinallikning cho'qqi qoplamasini aniqlash (NP-to'liq muammo).
4) Yo'naltirilmagan grafikning maksimal cho'qqi qoplamalarini aniqlash (NP-qiyin masala).
5) Grafik uchun Gamilton siklining mavjudligini aniqlash masalasi (NP-to'liq masala).
6) Sayohatchi sotuvchi muammosi: Har bir cho'qqida bitta hodisa bilan grafik bo'ylab optimal harakatni aniqlash (NP-qiyin muammo).
7) Rejalashtirish muammosi (NP-to'liq muammo).
Dostları ilə paylaş: | 
