|
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.
Dostları ilə paylaş: | 
