P=NP ? (Bilgisi olanlar, ilgilenenler)

[metboy]

P=NP problemi hakkında bilgisi, düşüncesi olan varmı. benim çok iligmi çekior aslında bu kadar bilgiyle pek fazla yorum yapamıorum. neyse problemi anlatan bi yazıyı yazıyorum. (yazı bi siteden değil bi dergiden alınmadır tek tek yazıyom :p )

P=NP?. Süper bilgisayarlarla yapılan şifreleme tekniğini tarihe gömecek olay "P'ye karşı Np" problemi bulunuyor. Bilgisayarcıların hangi algoritmanın hangi hesap işlemini hangi etkinlikte yapacağını araştırmalarıyla ortaya çıkmış. Genel olarak bir bilgisayar programına ne kadar çok veri yüklerseniz, programın bu verileri işleme süresi o ölçüde uzar. Bir dosyalar listesini alfabetik sıraya koyacak bir algoritma düşünün. Dosyaların sayısını ikiye katlarsınız, programın bunları sıraya koyması için gereken süre dörde katlanacaktır. Bilgisayar bilimi dilinde bu, bir N^2 algoritması. Pekçok işlem için programcılar bu gibi "polinomyal süre" ya da P algoritmalar kullanıyorlar; çünkü işlemlerin çözümü öyle göze alınmayacak kadar uzun olmuyor.
Çok haneli sayıların çarpanlarına ayrılması gibi polinomyal sürede çözülmeyecek problemler bile, polinomyal süre içinde sağlanabilir. Örneğin büyük bir sayıyı çarpanlarına ayırdığını söyleyen birinin doğru yapıp yapmadığını kontrol etmek için çarpaları birbirleriyle çarpmanız yeterli. Böyle polinomyal süre içinde kontrolü yapılabilecek bir probleme NP deniyor. Açık ki, tüm P algoritmaları birer NP; çünkü bir şeyi polinomyal süre içinde çözebiliyorsanız, başkasının bulduğu bir çözümüde polinomyal süre içinde kontrol edebilirsiniz. Gelegelelim 1971'de Computer bilimcisi Stephan Cook, bir NP algoritmasının aynı zamanda bi P algoritması olup olmadığını sordu.
"Yanıt olumsuz gibi. Büyük sayıları çarpanlarına bölmek gibisinden NP problemlerinin polinomyal süre içinde çözümünün bilinen örneği yok. Ancak bunu kanıtlamak göründüğü gibi kolay değil. Üstelik kanıt, ödülle birlikte hesapta olmayan başka şeyler de getirebilir! Matematikçiler "tam NP" denen ve NP problemlerinin en zor türü olan problemlerin birbirine eşit olduğunu kanıtladılar. Böyle olunca da bir tam NP problemin polinomyal süre algoritması, bu çeşit tüm problemlerin çözümü için uyarlanabilir. Cook, böyle bir algoritmayla her türlü şifreyi kırabiliriz." diyor.[hline]Kenderleme, 01 July 2003 03:18 tarihinde demiş ki:
midesini yıkarlardı adamın ne hap kalırdı ne metrikis kalırdı işte o zaman.

[Ceday]

çarpanlarına ayırma işlemi polinomial bir işlem..
bilgisayar mühendislerin ugrastıgı bütün problemler suan zaten PN tanımlamasında..onlardan sonra zaten x^N gibi problemler geliyor ki, onlarla pek ugrasılmıyor bile..
bir de programsal olarak çözümü imkansız olan sorunlar var..

[metboy]

ok saol[hline]Belphegor, 04 July 2003 23:41 tarihinde demiş ki:
muhahaha :hrr: