Mavzu: Algoritm murakabligini statik va dinamik o’lchovlari. Vaqt va xotira xajmi bo’yicha qiyinchiliklar

2.5.2 NP- qiyin vaNP- Vazifalarni bajaring.
P dagi muammo NP- qiyin agar uning yechimining DA (PDA) polinomi mavjud bo'lsa, undan NPga kiritilgan barcha masalalarning yechimini olish uchun foydalanish mumkin. Ya'ni, bunday muammo NP-qiyin, agar u hech bo'lmaganda NPdagi har qanday muammo kabi qiyin bo'lsa.
NP ga tegishli NP-qiyin masala deyiladi NP-to'la vazifa. Bunday muammolar har qanday NP muammosidan kam emas. Bundan tashqari, NP-qattiq yoki NP-to'liq masala uchun PDA mavjudligi P va NP sinflarining mos kelishini anglatadi, ya'ni 3-sinfning barcha masalalarini tezkor algoritm bilan hal qilish mumkin.
Muammoning NP-qiyinligini isbotlash uchun, agar muammo uchun PDA mavjud bo'lsa, u holda NPga kiritilgan muammolarning boshqa PDA yechimini olish uchun ishlatilishi mumkinligini ko'rsatish kerak.
Muammoning NP-to'liq ekanligini aniqlash uchun uning NPga tegishli ekanligini isbotlash kerak.
Bir masalani yechish algoritmidan boshqasini yechish algoritmini olish uchun foydalanish g‘oyasi algoritmlar nazariyasidagi eng muhim algoritmlardan biridir.
Ta'rif 1: R1 masala R2 muammosiga aylantiriladi, agar R1 muammoning har qanday maxsus holatini ko'pnomli vaqtda R2 muammosining qandaydir maxsus holatiga aylantirish mumkin bo'lsa. U holda R1 yechimini R2 muammoning xususiy holining yechimidan ko‘pnomli vaqtda olish mumkin.
https://pandia.ru/text/78/183/images/image024_39.gif "kenglik =" 158 balandlik = 56 "balandlik =" 56 ">
Masalan:
f2 (xi)=(x1 Ú x2 ) Ù ( ) Ù ()
mumkin emas, chunki hech kim uchun xi f2 (xi)= yolg'on.
Teorema :
Qoniqish muammosi NP-to'liq.
xi tanlash (to'g'ri, noto'g'ri)
agar E (x1, x2,…, xN) bo'lsa, muvaffaqiyat
boshqa muvaffaqiyatsizlik
P1 muammosini P2 ga aylantirishdan foydalanib, qoniqish muammosining cheklangan holati ham NP-to'liq ekanligini ko'rsatish mumkin.
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).