NP-to‘liqlik masalasining kuchlilik tomoni




Download 19,17 Kb.
bet3/3
Sana26.05.2024
Hajmi19,17 Kb.
#254358
1   2   3
Bog'liq
LGORITM2mavzu

NP-to‘liqlik 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).
Masalaning raqamli parametrlari mavjud bo‘lmasa (ya'ni, bu masalada uchraydigan kattaliklarning maksimal' qiymati polinom uzunligi bilan yuqoridan chegaralangan).
NP-to‘liqlik 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‘liqlik 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
Download 19,17 Kb.
1   2   3




Download 19,17 Kb.

Bosh sahifa
Aloqalar

    Bosh sahifa



NP-to‘liqlik masalasining kuchlilik tomoni

Download 19,17 Kb.