Mustaqil ishi qabul qildi: Ergashev. O topshirdi: Shamsuddinov. H mavzu: np- to’liq masalalar. Hisoblashda yechilmaslik hollari. Reja: np-to‘liklik masalasi

NP-to‘liklik masalasining kuchlilik tomoni

Agar masalaning qisim masalalari mavjud bo‘lsa u kuchli NP-to‘liq masala deyiladi, bunda: Masalaning raqamli parametrlari mavjud bo‘lmasa (ya’ni, bu masalada uchraydigan kattaliklarning maksimal qiymati polinom uzunligi bilan yuqoridan chegaralangan).

1. 
   Masalaning raqamli parametrlari mavjud bo‘lmasa (ya’ni, bu masalada uchraydigan kattaliklarning maksimal qiymati polinom uzunligi bilan yuqoridan chegaralangan).
   
2. 
   NP-to‘liklik masala.
   

Bunday vazifalar sinfi NPCS deb nomlanadi. Agar P ≠ NP gipotezasi to‘g‘ri bo‘lsa, unda NPCS masalasi uchun soxtaopolinomial algoritm mavjud emas.





NP-to‘liklik masalaga misollar

• 
  Bul formulalari bajarilishi masalasi
  
• 
  "Dog‘lar" n × n o‘lchamining eng qisqa yechimi
  
• 
  Kommivoyajyora masalasi
  
• 
  Shteyner muammosi
  
• 
  Grafani bo‘yash masalasi
  
• 
  Soxa (yuza) qoplamasi masalasi
  
• 
  To‘plamni qoplash masalasi
  
• 
  Tanlash masalasi
  
• 
  To‘plamning mustaqilligi masalasi
  
• 
  Saper (o‘yin)
  
• 
  Tetris
  

Ko'p qiziqarli va amaliy masalalarni polynomial vaqtda hal qilish mumkin emas yoki ular uchun hozirgi vaqtda polinomial algoritmlar topilmagan. NP(Nondeterminictic Polinomial) murakkablik sinfidagi masala - bu shunday masalalar sinfidirki, ularni yechish uchun polinomial algoritm mavjud bo'lmasligi mumkin, lekin agar biz uning yechimini bilsak (masalan, biz buni taxminan topgan bo’lsak), unda polinominal vaqt ichida uning to'g'riligini tekshirish mumkin. Ushbu sinf ichida NP-to'liq masalalarga alohida e’tibor beriladi.

Ushbu masalalarni hal qilish uchun polynomial algoritmlar hali topilmagan. Ammo bu sinfdagi barcha masalalarni bir-biriga keltirish mumkin. Ya'ni, agar NP to’liq masalalarning qandaydir birontasini polynomial vaqt ichida hal qilish mumkin bo'lsa, bu ushbu sinfdagi barcha boshqa masalalarpolinomial vaqtda samarali hal qilinishini anglatadi.
Bugungi kunga qadar, ko'pchilik mutaxassislar NP to’liq masalalarni polinomial vaqt ichida hal qilib bo’lmaydi, ya'ni NP≠P deb hisoblashadi (bu yerda P - polinomial vaqt ichida yechilishi mumkin bo'lgan masalalar sinfi), ammo buni isbotlay olmadilar. Ammo so'nggi paytlarda ushbu nuqtai nazarni inkor etishga urinishlar mavjud. Ya'ni, ushbu ilmiy munozaradagi nuqta hali aniqlanmagan. NP sinfidagi ko'pgina masalalar uchun (bunday masalalar bir necha minglab aniqlangan) yechimlarning samarali algoritmlari allaqachon ishlab chiqilgan yoki ularning to'liqligi isbotlangan. Shunga qaramay, ushbu masalada istisnolar mavjud.
NP to’liq masalarni hal qilishning keskin amaliy ehtiyojlari bizni ularni hal qilish bilan bog'liq qiyinchiliklarni yengish yo'llarini izlashga majbur qiladi. Bunday yo'llar sifatida quyidagilarni qayd etish mumkin: evristik (yaqinlashgan) yechimlarni topish, qidiruv algoritmlarini takomillashtirish, masalalarning o'lchamlariga eksponential darajada bog'liq bo'lgan jadvallardan foydalanuvchi dinamik dasturlash. Yangi masalaga duch kelinganda, birinchi navbatda savol tug'ilishi tabiiy: "Ko'rib chiqilayotgan masalani polinomial algoritm yordamida hal qilsa bo'ladimi?". Agar ushbu savolga javob ijobiy bo'lib chiqsa, unda NP-to'liqlik nazariyasi nuqtai nazaridan muammo haqida hech narsa deyish mumkin emas. Keyingi harakatlarimizni iloji boricha eng samarali polinomial algoritmlarni topishga jamlashimiz mumkin.
NP-to'liq masalani hal qilishning maqbul algoritmini topish muammosini hal qilishda ikkita toifadagi yondoshuv mavjuddir. Birinchi guruh qidiruv hajmini minimallashtirishga qaratilgan yondoshuvni o'z ichiga oladi, ammo ayni paytda eksponentsial vaqt sarf qilinishining muqarrarligi tan olinadi. Ketma-ket tanlab olish usuli uchun eng ko’p ishlatiladigan usullar qatoriga “tarmoqlar va chegaralar” usuli yoki "noaniq tanlab olish" usuliga asoslangan usullar kiradi.
Ikkinchi toifaga tegishli yondashuvlar faqat optimallashtirish masalalariga nisbatan qo'llaniladi (ammo bu juda kuchli cheklov emas, chunki amalda yuzaga keladigan juda ko'p masalalar optimallashtirish kabi shakllantirilgan) va "shartlarni kamaytirish" kabi usullarni o'z ichiga oladi. Bu optimal yechimni izlashdan voz kechish va maqbul vaqt ichida yaxshi yechimni topishdan iborat. Ushbu uslubga asoslangan algoritmlar odatda evristik yoki taxminiy deb nomlanadi, chunki ular qat'iy asoslashsiz turli xil mulohazalarni ishlatadilar.