P=NP P≠NP
Milenyum Problemleri olarak adlandırılan yedi problem 2000 yılında Clay Matematik Enstitüsü tarafından belirlenmiş matematiğin farklı dallarındaki yedi probleme verilen addır ve her birinin çözümü için verilen rakam 1 milyon $ . Kasım 2015 itibarı ile problemlerden altısı henüz çözülmemiştir. Bunlardan biriside 1971 den günümüze kadar üzerinde düşünülen KARMAŞIKLIK TEORİSİDİR.
Genel olarak matematik ve teorik bilgisayar biliminde cevap bekleyen akıl almaz sorulardan biridir.
Tanımla başlayacak olursak
p: "polynomial" ''polinom''
NP: "non-deterministic polynomial" ''belirleyici olmayan polinom''
Problemin çözümü için uygulayacagımız adımlar ne kadar az olursa verim ve işlem için kullanılan araç gereç ihtiyacı da o kadar az olur. Bundan kastımız formüller, yeni ihtiyaçlar, bilgisayar gereksinimleri vs.
Kimi problemler var ki çözümü elimizdeki imkanlarla çok kısa ve verimli bir şekilde sonuçlanırken, bir takım problemler ise çok uzun yıllar alıp verimsiz sonuçlanabiliyor.
Bu durumu örneklendirecek olursak iki tane n basamaklı sayının çarpımını ele alalım. Her basamagı birbiri ile çarpacagımızdan n^2 sonuçları ise n adımda olmak üzere tüm bu işlemi sonuçlandırmamız n^2+n basamakta sonuçlanır. 200 milyarı düşünürsek bu işlem 4.10^22+200.000.000.000 basamakta tamamlanıyor bu bile bilgisayarlarla işlem basamakları sürecinden çok uzun zaman alabiliyor.
Alman matematikçilerin önerdiği ancak kanıtlanamayan Schönlage-Strassen algoritması, “n-haneli sayıların çarpımı için esasen n*log
basit işlemini kullanarak oluşturulacak bir çözüm yolunun var olabileceğini" öngörmüştü. Makale söz konusu yöntemin, vakit alan işlemlere harcanan zamanı azalttığını kanıtlıyor. Milyar basamaklı sayılar, Schönlage-Strassen algoritmasıyla 30 saniyenin altında bir sürede çarpılabiliyor. Görüldügü üzere verim yeni gelişen problem çözme becerileri ile degişiyor.
Verimli çözümleri olan ve polinom zamanda çözülebilen problemlere P diyoruz.
10 kişilik bir gruptan 3 kişi seçmek sizler için zor olmasa gerek ki cevap 120 farklı şekilde seçim. Şimdi ise 200 kişiden 100 kişi seçmeyi deneyelim. Hepinizin aklında çözüm yolu belirdi ama işlem uzunlugunu fark edince kalem kagıt bile almadınız belki de elinize.
Burada kısa bir ara verip şimdiki yönümüzü faktöriyel kavramına çevirelim.
Gama fonksiyonunun tam sayılarla sınırlanmış özel bir durumudur faktöriyel ve bir sayının yanına (!) işareti konulması ile elde edilir ve1den başlanılarak o sayıya kadar olan sayıların çarpımı olarak ifade edilir.
Bu seçme işlemlerinde ise faktöriyel oldukça önemli bir yer tutar ancak üstte belirttigimiz problemde oldugu gibi yine oldukça zaman alacaktır işlem basamakları. Burayı biraz daha açalım isterseniz.
Matematikte Stirling yaklaşımı (ya da Stirling formülü) faktöriyel değerini çok yakın hesaplayan şuana kadar ki insanoğlunun elindeki sığındıgı tek formüldür.
logaritmalı tabiri ile formül ;
Logaritmiksiz ise ;
şeklinde ifade ediliyor.
Ancak formül çok büyük sayıların faktöriyelini hesaplamada yakın deger saglarken sayı küçüldükçe maalesef formülde sapmada o kadar artıyor.
şimdi ise vermiş oldugumuz problem degerini hesaplayacak olursak 200 kişiden 100 kişinin seçilmesi ;
9,0548×10^58 bu sayı bile muazzam büyüklükte. Düşünsenize 10 un yanında 58 sıfır var.
Bu işlem bile dakikada 60 milyar işlem yapan bilgisayarlar ile dahi 2,8538×10^42 yılda tamamlanıyor işte bu kadar uzun bir sürede. Bu sayıyı biraz açacak olursak Dünyamızdan Güneşe bu işlem tamamlanana kadar yaklaşık olarak 8,56164383×10^42 kere gidebilirdik. Çok uçuk rakamlardan bahsediyoruz , aslında problem basit gibi gözüküyordu yani 200 kişiden 100 kişi seçmek ne kadar zor olabilir diyenler için işte bu kadar zor olabilir. Dahası 1000 kişiden seçilen 10 kişiyi falan siz düşünün artık. Hatta düşünmeyin bile pek bir sonuca varamazsınız gibi.
NP ise bir probleme dair çözüm önerisi verildiginde bu önerinin polinom zaman sınırları içinde veriminin test edilmesi anlamına gelir. Yani bir yabancı geliyor ve diyor ki bu problemi x yolundan çözeceksin bizde bize verilen polinom zaman sınırları içerisinde bu x yolunun problemi çözmedeki dogrulugunu bulmaya çalışıyoruz.
Peki P=NP eşit olması ya da olmaması bizim için ne ifade ediyor ?
Soru diyor ki sonuçları verimli bir şekilde sınanabilen problemlerin (NP) aynı şekilde verimli çözümleri (P) bulunabilir mi?
Şifrelemelerimizin hepsi çok büyük sayıların asal çarpanlara ayrılmasının çok zor olması, yani bu problemin NP olmasına dayanıyor. Eğer bu probleme P’de bir çözüm bulunursa geçmiş olsun
Eger olurda iddia edildigi üzere bu eşitlik kanıtlanırsa hepiniz internete, login oldugunuz her yerdeki kişisel verilerinize, internet bankacılıgına, online alışverişe, sosyal medyanıza , şifre kullandıgınız her yere hoşça kal diyebilirsiniz.
Çünkü böyle bir durum P de çözülebilir her problemin NP de ise aynı şekil çözülebilecegi ya da NP çözümlü her bir problemin P yi de kapsayabilecegi anlamına geliyor ve yüksek güvenlikli şifreleri vs. çok daha hızlı ve verimli bir şekilde kırmaya ortam hazırlıyor. Aslında bize x yolundan git diyen o yabancının dedigi x yolu gerçekten dogru oluyor polinom zamanda.
Tartışmalar ne düzeyde ?
Bigisayar uzmanı olan Vinay Deololikar ortaya attıgı p≠np yazısı ile ortalıgı birbirine kattı resmen. Bir çok profesör ve blog yazarları , matematikçiler olaya el attılar. 1 haftalık çalışmanın ardından ''ciddi yanlışlıklar'' oldugu ileri sürüldü. Buna ragmen hazırladıgı 100 sayfadan fazla ve oldukça ileri düzey matematik içeren bu çalışma herkesin bakış açısını degiştirdi. Olaya çok farklı bir zemin hazırladı. Ortaya atılan MAKALE İÇİN TIKLAYIN
Hep kötü yanlarımı var bu eşitligin?
Tabi ki hayır.
İnterneti altüst ettikten sonra ülkeler için ekonomide, bilim için ise pratikte çok büyük ve verimli bir dönemi başlatacaktır.
Büyük bilgisayar bilimciler ne internetin karanlık sulara gömüleceğine ne de büyük verimlilik çağının başlayacağına ihtimal vermiyorlar.
Ancak ''KUANTUM BİLGİSAYAR'' çağı insan beklentisinin üstünde gelişmekte ve ülkelerden ardı ardına bu devasa yapılarla ilgili son dakika gelişmeleri gelmektedir. En son ÇİN, GOOGLE'den 100 milyar kat hızlı süper kuantum bilgisayarını sergiledi. Durum böyle olunca bu tartışmalarda hiç dinmeyecek gibi.
Daha fazla bilgi için inceleyebileceginiz yazı: Plus MaThs Dergisi
kaynakça: 1, 2 , 3
