P vs NP problem haqida ko'pchilik bilsa kerak, bilmaydiganlar bo'lsa shu joyida to'xtab, o'rganib kelsangiz bo'ladi. Ko'pchilik P=NP ekanini isbotlash faqat RSAga o'xshash assimmetrik kriptografiyani buzishga yordam beradi deb o'ylaydi. Aslida esa RSAni buzish shunchaki xamir uchidan patir.

Biror masala NP bo'lishi uchun uni deterministic approachda polynomial vaqtda yecha oladigan algoritmni bilmasligimiz, lekin potensial yechim berilsa yechim to'g'ri yoki noto'g'riligini polynomial vaqtda tekshirib ko'ra olishimiz kerak. Ya'ni NP masalalar qaysidir P ("oson") masalaning "teskarisi". Masalan, tub ko'paytuvchilarga ajratish (prime factorization) NP masala. Deylik, 4187 sonini tub ko'paytuvchilarga ajratish "qiyin", lekin 53 va 79 berilsa rostdan ham ularning ko'paytmasi 4187 bo'lishini oson aniqlay olamiz.

Demak bizda shunaqa funksiya borki, unga NP masala javobi input sifatida berilsa u to'g'ri yoki noto'g'ri ekanini polynomial vaqtda ayta oladi. "Switching Circuit Theory" (O'tkazgich sxemalari nazariyasi)ga ko'ra agar input uzunligi chekli deb olinsa bu turdagi har qanday funksiyani "AND", "OR", "NOT"ga o'xshash mantiqiy bloklar kombinatsiyasi (sxema) sifatida tasvirlash mumkin.

NP-complete savollar orasida Satisfiability problem (qanoatlantirish masalasi) nomli masala bor. Deylik, sizda bir qancha mantiqiy o'zgaruvchilar va mantiqiy operatorlardan iborat mantiqiy ifoda bor. Masala sharti, o'zgaruvchilarga qanday qiymat berilsa umumiy ifoda True (Rost) qiymatga ega bo'lishini topish.

Biz tepada aytgan mantiqiy bloklar kombinatsiyasini ham mantiqiy ifoda sifatida yozsak bo'ladi. Faqat har bir mantiqiy operator qanday ishlashi kerakligini qoidalar shaklida kiritish uchun yana qo'shimcha ifodalar qo'shish kerak bo'ladi (masalan, AND bloki faqat ikkala input ham true bo'lganida true natija qaytaradi). Natijada SAT masalasining xususiy ko'rinishi, CIRCUIT-SATga ega bo'lamiz.

Xo'sh, CIRCUIT-SAT nima qila oladi? Unga ma'lum natija berilsa shu natijaga erishish uchun mantiqiy sxemaga qanday input kiritish kerakligini aniqlay oladi. Har qanday chekli matematik funksiyani mantiqiy sxema sifatida tasvirlashimiz mumkinligini eslasak, demak u har qanday funksiyadan ma'lum bir natijani olish uchun unga qanday qiymat(lar) berish kerakligini aniqlay oladi. Ya'ni u har qanday funksiyani "orqaga qaytara oladi". Har qanday shifr, har qanday ma'lumotni qayta ishlash farqi yo'q. Funksiyaning o'zi deterministik bo'lsa bo'ldi.

Qisqa qilib aytganda, P=NP ekanini isbotlash bizga har qanday algoritmni tezda "orqaga qaytarish" imkoniyatini beradi. Lekin hali isbotlay olganimiz yo'q. Bu degani, bizda hozir ham har qanday funksiyani "orqaga qaytara oladigan" algoritmlarimiz bor, lekin ular hozircha juda sekin ishlaydi. Masalan, RSAda ishlatiladigan 2 ta 200 xonali atrofidagi sonlarni ko'paytirishni "orqaga qaytarish" uchun hozirgi algoritmlarga yuzlab yoki minglab yillar vaqt kerak bo'ladi.

P.S. Mavzuni chuqur bilmasligim yoki postni soddalashtirish maqsadida qilingan xatolar bo'lishi mumkin.

@boboshersnotes