Laboratoriya mashg’ulotlari mavzulari

Amliy qism
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.
LABORATORIYA ISHI - 26
Mavzu: NP-to’liq masalalarga keltirish usullari.
Ishdan maqsad. NP-to’liq masalalarga keltirish usullarini o’rganish.
Qo’yilgan masala. NP-to’liq masalalarga keltirish usullari.
Ish tartibi:

• 
  Tajriba ishi nazariy ma’lumotlarini o‘rganish;
  
• 
  Berilgan topshiriqning algoritmini ishlab chiqish;
  
• 
  C++ dasturlash muhitida dasturni yaratish;
  
• 
  Natijalarni tekshirish;
  
• 
  Hisobotni tayyorlash va topshirish.