WikiDer > Past va yuqori darajadagi ierarxiyalar
Low and high hierarchies
In hisoblash murakkabligi nazariyasi, past ierarxiya va yuqori ierarxiya murakkablik darajalari 1983 yilda kiritilgan Uve Shoning ning ichki tuzilishini tavsiflash uchun murakkablik sinfi NP.[1] Past darajadagi ierarxiya boshlanadi murakkablik sinfi P va "yuqoriga" o'sadi, yuqori ierarxiya esa NP sinfidan boshlanadi va "pastga" o'sadi. [2]
Keyinchalik bu ierarxiyalar NP tashqarisidagi to'plamlarga kengaytirildi.
Yuqori / past darajadagi ierarxiyalar doirasi faqat shu taxmin asosida mantiqiy ahamiyatga ega P NP emas. Boshqa tomondan, agar past darajadagi ierarxiya kamida ikkita darajadan iborat bo'lsa, unda P NP emas.[3]
Ushbu ierarxiyalar barcha NPni qamrab oladimi yoki yo'qmi noma'lum.
Adabiyotlar
- ^ Uve Shoning (1983). "NP tarkibidagi past va yuqori ierarxiya". J. Komput. Syst. Ilmiy ish. 27 (1): 14–28. doi:10.1016/0022-0000(83)90027-2.
- ^ "Murakkablik nazariyasi va kriptologiya", muallif Yorg Rot p. 232
- ^ Leyn A. Hemaspaandra, "Egasi: NP-P uchun mezon", ACM SIGACT yangiliklari, 1993, j. 24, № 2, 11-14 betlar. doi:10.1145/156063.156064
| P ≟ NP | Bu nazariy informatika- tegishli maqola a naycha. Siz Vikipediyaga yordam berishingiz mumkin uni kengaytirish. |