|
p va NP sinflari
Argumentning musbat tamsayı qiymatlari uchun aniqlangan haqiqiy salbiy funktsiya \\ (f (m) \\), haqiqiy koeffitsientli \\ (f (m) \\) polinom mavjud boʻlsa, polinom chegaralangan deyiladi. m) \\ leq P (m) \\) barchasi uchun \\ (m \\ in N ^ + \\). "Polinom" ish vaqti bilan algoritmlar mavjud boʻlgan masalalar P sinfiga tegishli (bu masalalar umuman tez va muammosiz echiladi).
Rasmiy taʻrif. L tili P sinfiga kiradi, agar u faqat deterministik Turing mashinasi M boʻlsa, shunday boʻladi:
Har qanday kirish maʻlumotlari uchun M polinom vaqtida oʻz ishini tugatadi,
- barchasi uchun \\ (x \\ in L \\) M 1 natija beradi,
- \\ (L \\) ga tegishli boʻlmagan barcha \\ (x \\) uchun M 0 natijani beradi.
NP sinfidagi muammolar- shartni qondiradigan muammolar: agar javob boʻlsa (mumkin boʻlgan echim) boʻlsa, unda uni tekshirish oson - uning echimi yoki yoʻqligini tekshirish.
NP sinfidagi muammoning misolini koʻrib chiqing. Butun sonlar toʻplami berilsin, masalan (-7, -3, -2, 5, 8). Siz ushbu raqamlar orasida 0 ga qoʻshiladigan 3 ta raqam mavjudligini bilmoqchisiz, bu holda "ha" deb javob beriladi (masalan, bunday uchlik raqamlar (-3, -2.5). butun sonlar toʻplamining koʻpayishi, 3 ta elementdan iborat kichik toʻplamlar sonining koʻpayib borishi, agar bizga bunday kichik toʻplam berilgan boʻlsa (sertifikat deb ham ataladigan boʻlsa), unda biz uning elementlari yigʻindisi 0 ga tengligini osongina tekshirishimiz mumkin.
Rasmiy taʻrif:
L tili NP sinfiga kiradi, agar u faqat \\ (p \\) va \\ (q \\) polinomlari va deterministik Turing mashinasi M mavjud boʻlsa, shunday boʻladi:
Har qanday \\ (x, y \\) uchun M kirish mashinasi \\ ((x, y) \\) maʻlumotlarga \\ (p (| x |) \\) vaqt ichida ishlaydi,
- har qanday \\ (x \\ in L \\) uchun \\ (y () \\) uzunlik \\ (q (| x |) \\) qatori mavjud boʻlib, u \\ (M (x, y) \u003d 1 \\),
- har qanday \\ (x \\) uchun \\ (L \\) dan emas va barcha uzunlik satrlari uchun \\ (q (| x |) \\) \\ (M (x, y) \u003d 0 \\).
Polinomning kamaytirilishi yoki Karpning pasayishi. \\ (F_1 \\) funktsiyasi, har qanday \\ (x \\) \\ (f_ (1) (x) \u003d f_ () uchun funktsiya mavjud boʻlsa, u holda \\ (f \\ ning P \\) funktsiyasi \\ (f_2 \\) ga kamayadi. 2) (f (x)) \\).
Muammo T deyiladi Toʻliq emasagar u NP sinfiga tegishli boʻlsa va NP dan boshqa har qanday muammo polinom vaqtida unga kamaytirilsa. Ehtimol, NP bilan toʻldirilgan muammoning eng mashhur namunasi SAT (qoniqish uchun) muammosi boʻlishi mumkin. Mantiqiy oʻzgaruvchilar, "AND", "OR", "NOT" operatorlari va qavslarni oʻz ichiga olgan formula berilsin. Vazifa quyidagicha: formuladagi barcha oʻzgaruvchilarga qiymatlarni berish mumkinmi? yolgʻon va toʻgʻri shunday qilib formula "qiymatini oladi" toʻgʻri".
Muammo T deyiladi Qattiq-qattiqagar u uchun polinom vaqtida T ga kamaytiradigan NP-toʻliq muammo boʻlsa. Bu erda oshpazning pasayishi nazarda tutilgan. Kuk boʻyicha \\ (R_1 \\) \\ ni \\ (R_2 \\) ga kamaytirish bu muammoning echimini topadigan funktsiya \\ (R_2 \\) berilishi sharti bilan \\ (R_1 \\) muammoni echadigan polinom vaqt algoritmidir. uni oracle sifatida, yaʻni unga kirish faqat bir qadamni oladi.
Yuqorida keltirilgan muammolar sinflari oʻrtasidagi mumkin boʻlgan munosabatlar (olimlar P va NP bir xil ekanligiga hali ham amin emaslar).
Qiyinchilik funktsiyasi 0 (1). Doimiy murakkablik algoritmlarida dasturdagi aksariyat amallar bir yoki bir necha marta bajariladi. Har doim bir vaqtning oʻzida talab qilinadigan har qanday algoritm (maʻlumotlar hajmidan qatʻi nazar) doimiy murakkablikka ega.
Murakkablik funktsiyasi 0 (N). Dasturning ishlash vaqti odatda chiziqli boʻladi, chunki kirish maʻlumotlarining har bir elementi faqat chiziqli ishlov berilishi kerak. Ushbu murakkablik funktsiyasi oddiy tsiklni tavsiflaydi.
Murakkablik funktsiyasi 0 (N 2), 0 (N 3), 0(№) - polinom murakkabligi funktsiyasi: operatsiyalar soni kvadratga mutanosib ravishda oʻsadi N. Umumiy holda, masalaning murakkabligiga qarab O (A ^) boʻlishi mumkin. Ushbu murakkablik funktsiyasi murakkab tsiklni tavsiflaydi.
Do'stlaringiz bilan baham: |
