Ko'proq atamalar va ta'riflar: -
•
NP-qiyin - agar X
∈
NP X-ga tushadigan bo'lsa, X muammosi
kamida NPda hal
qilinadi
, masalan NP-ning har bir muammosini hal qilish qiyin (agar P! = NP
bo'lsa, unda X P ga tegishli bo'lmaydi).
•
Reduksiya - A muammoni kiritishlarni ko'paytma
vaqt algoritmidan foydalanib
, B
muammosining ekvivalent kirishiga aylantirish jarayoni.
Ekvivalent degani
, A va B
muammolari kirish va o'zgartirilgan kirish uchun bir xil javobni (Ha yoki Yo'q)
berishi kerak. A dan B gacha qisqartirish algoritmining mavjudligi quyidagilarni
nazarda tutadi:
1. Agar B
∈
P bo'lsa, u holda A
∈
P (ko'paytmali vaqt ichida A dan B gacha
qisqartirishingiz mumkin va B polinomik vaqt ichida echishingiz mumkin. Buni
birlashtirish A uchun ko'p vaqtli algoritmni beradi)
2. Agar B
∈
NP bo'lsa, unda A
∈
NP
3. Agar A NP-qattiq bo'lsa, B - NP-qattiq. A ko'paytirilgan vaqt ichida B ga kamayishi
mumkin va agar B NP-qiyin bo'lmasa, u B B NP-NP-qiyin va bu A
∈
NP-NP-qattiq
, bu
farazga zid (A-NP-qiyin) degan ma'noni anglatadi.
•
NP-to'liqligi - agar X
∈
NP va X bo'lsa, NP-qiyin bo'lsa, X muammo NP-
tugallanadi.
•
Muammo
NP-tugaganligini isbotlash
Muammoning to'liqligini isbotlash 2 bosqichni o'z ichiga oladi. Avval biz muammo
NPga tegishli ekanligini ko'rsatishimiz kerak va keyin biz buni NP-qiyinligini
ko'rsatishimiz kerak. Bosqichlarni quyidagicha izohlash mumkin:
1-qadam - X
∈
NP ni ko'rsatish. X uchun netereterministik algoritmni toping.
Ammo amaliy usul, agar potentsial echim taqdim etilsa, X uchun ko'paytmali vaqt
tekshiruvini o'tkazishdir.
2-qadam - X-ni ko'rsatish qiyin emas. Ma'lum NP-muammoni X-ga qisqartirish.
Demak, biz ko'rgan 3-rasm orqali X bu NP-qiyin ekanligini anglatadi.
•
Bu masala qisqa P va NP murakkab sinfi tengmi?
•
P-
sinfi deb kompyuter “tezda”(“Birzumda”) yechimi mumkin bo’lgan masalalar
majmuiga aytiladi. Bunga arifmetik amallarning asosi (negizi) ro’yh
atlarni
saralash, jadval bo’yicha ma’lumotlarni izlash kiradi.
NP-
sinfiga javobning to’g’riligini tezda tekshirish mumkin bo’lgan masala kiradi.
Masalan: faraz qilaylik sizda qiymati 2,3,5,6 va 7 so’mlik tangalardan bittadan bor
va siz narxi 21 so’m bo’lgan harid uchun qaytimsiz to’lashni hoxlamoqdasiz.
Ulardan yig’indisi 21 so’m bo’lgan tangalarni yig’ib olish mumkinmi?
Bu masalaga javob olish uchun har hil variantni tanlash lozim, agar masala
yechimini yo’qligini isbotlasmoqchi bo’lsak, umuman olganda barcha bo’lishi
mumkin bo’lgan variantlardni tanlash lozim. Agar tangalar sonini bir necha usulda
ko’paytirsak yechish mutlaqo nomuvofiq ko’rinishda bo’ladi. Bunda natijani oson
tekshirish uchun shunchaki barcha “ming yillik masalasi” ning mohiyati
quyidagich
a (bunday) ifodalanadi (ta’riflanadi): P va NP sinflari tengmi? Agar
masala yecvhimining to’g’riligini tekshirish oson bo’lsa, masalani o’zini yechish
ham oson bo’lishi mumkinmi?
Ko’pchilik mutaxassislar javobning yo’qligi (salbiy)ga amindirlar, lekin buni
hozircha hech kim isbotlay olgani yo’q agar P=NP bo’lib qolsa, unda insoniyatni
kriptografiyaga (sirli belgi va ishoralar bilan yozish tizimi) keskin burilish
ko’taradi.
NP-
to’liqlik
masalasi
Amaliy nuqtai nazardan qiziq bo‘lgan
vazifalarning aksariyati
, polinomial'
(polinomial' vaqt mobaynida ishlovchi) algoritmlar. Ya'ni, n uzunlikdagi kirishda
algoritmning ishlash vaqti doimiy k (kirish uzunligidan mustaqil) uchun O(nk) dan
oshmaydi. Har bir masalada ushbu xususiyatni qondiradigan yechim algoritmi
mavjud emas. Ba'zi masalalarni umuman biron bir algoritm yordamida hal qilib
bo‘lmaydi. Bunday masalaning klassik misoli bu “to‘xtash muammosi” (berilgan
dastur
berilgan kirishda to‘xtashini bilish). Bundan tashqari, ularni hal qiladigan
algoritm mavjud bo‘lgan masalalar mavjud, har qanday bunday algoritm uzoq
vaqt ishlaydi
–
uning ishlash vaqti har qanday fiksirlangan k soni uchun O(nk)
bo‘la olmadi.
Agar biz am
aliy algoritmlar va faqat nazariy qiziqish algoritmlari o‘rtasida qo‘pol,
ammo rasmiy chegara chizishni istasak, unda ko‘plikli vaqt ichida ishlaydigan
algoritmlar sinfi birinchi o‘rinda turadi. NP
-
to‘liq deb nomlangan masalalar sinfini
ko‘rib chiqamiz. U
shbu masalalar uchun hech qanday polinomial' algoritmlar
topilmagan, ammo bunday algoritmlar mavjud emasligi isbotlanmadi. NP bilan
bog‘liq muammolarni o‘rganish “P = NP” deb nomlangan savol bilan bog‘liq. Bu
savol 1971 yilda berilgan va hozirda hisoblash nazariyasida eng qiyin
masalalardan biri hisoblanadi.
Nima uchun dasturchi NP
–
tugallangan masalalar haqida bilishi kerak? Agar
biron bir NP
–
to‘liqlik uchun uning to‘liqligini isbotlash mumkin bo‘lsa, uni deyarli
hal qilib bo‘lmaydi deb hisoblash uchun
asos bor. Bunday holda, uni aniq hal
qiladigan tezkor algoritmni qidirishni davom ettirishdan ko‘ra, taxminiy algoritmni
tuzishga vaqt sarflash yaxshiroqdir.
Polinom vaqti.
Abstrakt masalalar
Yuqorida aytib o‘tilganidek, ko‘p jihatdan hal qilinadigan (polinomial) masalalar
konsepsiyasi amalda yechilishi mumkin bo‘lgan masalalar g‘oyasini
takomillashtirish hisoblanadi. Ushbu kelishuvni nima tushuntiradi? Birinchidan,
amalda ishlatiladigan ko‘pay
tirilgan algoritmlar, odatda juda tez ishlaydi.
Ikkinchidan, polinomial algoritmlar sinfini ko‘rib chiqish, bu sinfning hajmi ma'lum
bir hisoblash modelini tanlashdan deyarli mustaqil bo‘lishidir. Masalan, tasodifiy
tasodifiy kirish mashinasida (RAM) ko‘pa
ytirilgan vaqt ichida yechilishi mumkin
bo‘lgan masalalar sinfi T'yuring mashinalarida polinomal yechiladigan masalalar
sinfiga to‘g‘ri keladi. Sinf parallel hisoblash modeli uchun bir xil
bo‘ladi,
prosessorlar soni, kirish uzunligi polinomi bilan cheklangan. Uchinchidan,
polinomal yechiladigan masalalar sinfi tabiiy yopiqlik xususiyatlariga ega.
Masalan, ikkita algoritmning tarkibikompozisiyasi ham polinomial vaqtli ishlaydi.
Buning sababi, ko‘pxadlarning yig‘indisi, ko‘paytmasi va kompozisiyasi
ko‘pxadrdi
r.
Quyida hisoblash masalasining abstrakt modelini keltirilgan. Buni
abstrakt masala
deb nomlaymiz
, Q
–
ikkita to‘plam elementlari orasidagi ixtiyoriy binar
munosabat: I
–
sh
artlar to‘plami va S –
yechimlar to‘plami.
Masalan,
G=(V,E)
yo‘naltirilmagan grafning berilgan ikkita uchlari orasidagi eng
qisqa yo‘lni topish masalasida, shart (element I) uch element, graf va ikkita
qirradan iborat va yechim (S element)
–
bu grafda kera
kli yo‘lni tashkil etuvchi
vertikallarning ketma-ketligi.
NP to‘liqligi nazariyasida faqat hal qilish masalalari ko‘rib chiqiladi –
muayyan
savolga “ha” yoki “yo‘q” deb javob berish kerak bo‘lgan masalalar. Rasman, I
to‘plam shartlarini
{0,1}
to‘plamga to‘g‘ri keladigan funksiya sifatida ko‘rib
chiqilishi mumkin. Masalan,
G=(V,E
) grafdagi eng qisqa yo‘lni topish masalasi
bilan berilgan
G=(V,E) graf yordamida ikkita tugun u, v
∈
V va natural k butun
sonlar u va v tugunlari orasida undan katta bo‘lmagan hamda G grafda yo‘l bor
yoki yo‘qligi masalasini yeching.
Optimallashtirish bilan bog‘liq masalalar bu –
muayyan miqdordagi qiymatni
maksimal darajada oshirish yoki minimallashtirish kerak bo‘lgan masalalardi. NP –
to‘liqlik haqida savol berishdan
oldin bunday masalalar
, ularni hal qilish
masalalariga aylantirilishi kerak. Shunday qilib, masalan, grafdagi eng qisqa yo‘lni
topish masalasida optimallashtirish masalasini yechish masalasidan ruxsat berish
masalasiga o‘tdik va yo‘l uzunligiga cheklov qo‘shdik. Agar transformasiyadan
keyin NP
–
to‘liq
masalasi yuzaga kelsa, unda asl muammoning qiyinligi ham
belgilanadi. Ma'lumotlar taqdimoti
Kirish ma'lumotlarini (y
a'ni I to‘plamning elementi) algoritmga kiritishdan oldin
ularning qanday qilib “kompyuterga qulay” tarzda taqdim etilishi to‘g‘risida
kelishib olish kerak. Dastlabki ma'lumotlar bitlar ketma-ketligi bilan kodlangan
deb qabul qilamiz. Formal aytganda, S to
‘plamining elementlarini ifodalash bu S
dan e ni bitli satrlar to‘plamlariga tushishidir. Masalan
, (0, 1, 2, 3,...)
–
butun
sonlarni, odatda
(0, 1, 10, 11, 100, ...)
–
bitli satrlar bilan ifodalanadi.
Taqdim qilingan ma'lumotlarni joylashtirb, mavhum masalani satrli
ma'lumotga
aylantiramiz
, bu satirli ma'lumot uchun kirish ma'lumotlari,
masalaning dastlabki ma'lumotlarini aks ettiruvchi bitli satir bo‘la
di. Kirish
ma'lumotlari (bitli satr) n
–
uzunlikda bo‘lganida, algoritmning ishlash
vaqti
O(T(n))
–
bo‘lsa, algoritm satirli masalani
O(T(n)) vaqtda yechadi desak
bo‘ladi. Agar k konstanta va
O(T(n)) vaqt ichida bu masalani yechadigan algoritm
mavjud bo‘ls
a, satirli masala polinomial' deb ataladi. Murakkablik P sinfi
–
bu
barcha satirli masalalar bo‘lib, polonomia' vaqt ichida yechilishi mumkin,
ya'ni,
O(n
k
)
vaqt ichida yechilishi mumkin, bu yerda k kirishga bog‘liq bo‘lmaydi.
Polinomial abstrakt masalasining konsepsiyasini aniqlashni
istagan holda
, biz turli
xil ma'lumotlarni taqdim etish mumkinligiga duch kelamiz.
Xar bir taqdim qilingan e to‘plam uchun, I kirishlari bo‘lgan Q abstrakt
masalaning satirli masalasini olamiz.
Biroq, amalda (asosi 1 bo‘lgan raqamli tizim kabi “qimmat” vakillik usull
arini
istisno qilsak), tabiiy vakillik usullari odatda ekvivalentdir, chunki ularni bir-biriga
ko‘p jihatdan aylantirish mumkin. A polinomial algoritmi mavjud
bo‘lsa,
f
:{0,1}*→{0,1}* funksiyasi polinimial vaqt ichida hisoblab chiqiladi, u har
qanday x
∈
{0,1}* uchun f(x) natijani beradi.
Ixtiyoriy abstrakt masala uchun I to‘plami sharitlarini ko‘rib chiqamiz. I
to‘plamning
е
1 va
е
2
elementlari polinomial' bog‘langan deyiladi, agar polinomial'
vaqtda hisoblash mumkin bo‘lgan ikkita
f
12
(
e
1
(
i)) = e
2
(
i) va f
21
(
e
2
(
i))
=
e
1
(
i), i
∈
I
funsiyalar mavjud bo‘lsa. Bunday hollarda, polinomial' bog‘langan
ikkita elementdan qaysi birini tanlash muhim emas.
P, NP, NP-complete (NP-
to‘liklik masalalari) sinflar orasidagi munosabatlar,
NP-
hard (NP-
murakkab masalalar), P≠NP va P=NP bo‘lgan xollarda.
NP- tuliklik masalasi
—
algoritmlar nazariyasida NP
–
sinfdagi «ha» yoki «yo‘k»
javobli masalani shu sinfdagi boshka masalaga polinomial' vakt oralgida
moslashtirish mumkin (yani, boshlangich ma'lumotlar xajmiga boglanganlik
darajasi ma'lum polinimdan katta bulmagan amallar yordamida bajariladi).
Shunday qilib, NP -
to‘liq
masalalar
, ma'lum ma'noda, NP sinfidagi “tipik”
masalala
r to‘plamini shakllantiradi: agar ularning ba'zilari uchun "tezkor" yechim
algoritmi topilsa, NP sinfidagi har qanday boshqa masalani xuddi shu tarzda hal
qilish mumkin.
Formal' ta'rif
Alifbo deganda har qanday cheklangan belgilar to‘plami tushuniladi (masalan,
{0,
1} yoki {a, b, c}
). Ixtiyoriy ∑ alifbosidan tuzilgan barcha so‘zlar to‘plami (yozilgan
satirlar, ushbu alifboning belgilaridan tashkil topadi) ∑* bilan belgilanadi.
∑ alfavit
yordamida yaratilgan ixtiyoriy L tili bu ∑^* to‘plamning L to‘plam ostisi,
ya'ni L
⸦∑^*.
•
L uchun tanib olish vazifasi berilgan so‘z L tiliga tegishli yoki yo‘qligini aniqlashdir.
•
∑ alifbo ustida
va -
ikkita til bo‘lsin.
tiliga (Karp bo‘yicha)
L
2
tiliga qisqartirish
deyiladi, agar
funksiyasi mavjud bo‘lsa, bu funksiyani polinomial' vaqt bilan
hisoblash mumkin bo‘lsa, quyidagi xususiyatga yega: :
x
∈
L
1
, , agar va faqat
agar .
Karp bo‘yicha qisqartirish
L
1
≤
p
L
2
bilan belgilanadi.
•
Agar NP-dan biron bir til unga qisqartirilsa, tili NP-
to‘liq deb nomlanadi.
Til NP-
mukammal deb nomlanadi
, agar u NP-
qiyin bo‘lsa va shu bilan birga o‘zi NP
sinfida bo‘lsa.
•
A masala B masalasiga qisqartirilganligi, A
masala B masalasidan ko‘ra
“murakkabroq” ekanligini anglatadi (chunki agar biz B masalani yechilishi, A
masalanini ham yechilishini bildiradi). Shunday qilib, NP bilan bog‘liq qiyinchiliklar
sinfga NP bilan bog‘liq masalalar va ular uchun "ancha qiyin" bo‘
lgan masalalar
kiradi (ya'ni NP bilan bog‘liq masalalarni kamaytirish mumkin bo‘lgan masalalar).
NP sinf NP to‘liq masalalarni va ulardan "osonroq" bo‘lgan masalalarni o‘z ichiga
oladi (ya'ni, NP-
to‘liq masalalarga qisqartirishgan masalalar).
•
Ta'rifdan shunday xulosa kelib chiqadiki, agar NP-
to‘liq masalasi polinomial'
vaqtda hal qiladigan algoritm topilsa, unda barcha NP-
to‘liq masalalar
P sinfga
joylashtiriladi
, ya'ni ular polinomial' vaqtda yechiladi.
Do'stlaringiz bilan baham: |