Görsel açıklaması: Yeni geliştirilen matematiksel algoritma izomorfik graf problemine meydan okuyor ve iki farklı ağın (network) karşılaştırılıp, bu iki ağın aslında aynı olup olmadığının, daha önce kullanılan algoritmalardan çok daha az basamakta belirlenmesini sağlıyor. Uyarlama Booya Bazooka.
Kompleksite teorisinde senelerden sonra en büyük ilerleme söylentisi günlerdir internet ortamını aydınlatıyor. László Babai, Şikago Üniversitesi’nde matematikçi ve bilgisayar bilimci, geliştirdiği matematiksel algoritma ile iki farklı ağı (network) karşılaştırıp (ağların ne kadar büyük ve karışık olduğu önemli değil), bu iki ağın (network) aslında aynı olup olmadığını, daha önce kullanılan algoritmalardan çok daha az basamakta belirtiyor. Bilgisayar bilimcilerin çözülmesi zor olarak gördükleri problemlerden birine açıklama gelmesi, onları oldukça heyecanlandırdı.
MIT bilgisayar bilimcisi Scott Aaronson, bu sonucun doğru olması durumunda, teorik bilgisayar biliminin on yılının bir sonucu olabileceğini belirtti.
Karmaşıklık teorisi, temelde, bilgisayar ile neyin kolay, neyin zor çözülebileceğinin incelenmesidir. Araştırmadaki önemli nokta; problemi çözmek için gerekli olan adımların, girdilerin (inputs) boyutu ile beraber nasıl büyüdüğüdür. Örneğin 983 veya 105227 sayılarının asal olup olmadığı belirlemek istiyoruz. Bu hesaplamadaki bilgisayımsal (kompütasyonel) adımlar, sayının içindeki rakamların sayısına göre yavaşça büyür. Genellikle, bilgisayımsal adımlar rakamların sayısına “n” dersek, “n” ile üslü fonksiyon oluşturacak şekilde büyür; yaklaşık olarak n2 diyebiliriz. Bu tarz ifadeler polinom olarak ifade edilir ve problemin polinom zamanda çözülebildiği belirtilir ve bu problemin karmaşıklık sınıfı “P”ye aittir.
Diğer bir yandan ise, 21, 122, 331 sayılarını tüm çarpanlarına (faktörlerine) bölmek istediğimizi düşünelim. Hiç kimse bu problemin çözümü için bu zamana kadar polinom zaman algoritması bulamadı. Bu yüzden faktöring probleminin çok daha zor olduğu düşünülür ve bu problem “NP” (belirleyici olmayan polinom) karmaşıklık sınıfına aittir. Daha zor “NP” problemleri için konuşmak gerekirse, bilgisayımsal adımlar, girdilerin sayısı ile beraber üstel fonksiyon oluşturacak şekilde artar; yaklaşık olarak 2n diyebiliriz. (Örneğin, n=100 olduğu zaman, polinom fonksiyonumuz n2=1002=10.000 olur, fakat üstel fonksiyonumuz 2n=2100 olur ve bu sonuç polinom fonksiyonunun verdiği sonuçtan milyarlarca, trilyonlarca kat fazladır.)
Babai daha zorlu “NP” problemlerinin tayfın diğer tarafındaki kolay “P” problemlerine yaklaşabileceğini gösterdi. İnsanların gribi yaymasını veya organizmaların içindeki proteinlerin etkileşimini temsil eden herhangi bir ağ (network), düz çizgilerle birbirine bağlı ve birbirleriyle etkileşim halinde noktalar, düğümler (nodlar) kümesi olarak tarif edilebilir. Çünkü düğümler (nodlar) keyfi bir şekilde yerleştirilebilir, aynı bağlantı düzenlemesine sahip iki grafik farklı gözükebilir (şekildeki gibi), özellikle grafik büyüyüp karmaşık hale geldikçe.
İzomorfik graf probleminde zorluk iki grafiğin aynı olup olmadığını belirlemekti. Babai bugün duyurduğuna göre; bu problemi çözebilecek bir algoritma geliştirdi.
Eugene Luks’un, 1983 yılında geliştirmiş olduğu yöntemde bilgisayımsal adımların sayısı, ağdaki düğümlerin sayısı ile beraber üssel olarak artıyordu. Babai’nin algoritmasında ise bilgisayımsal adımların sayısı, polinomial zamandan biraz hızlı olarak artıyor. Grinin tonlarını karşılaştırmak gibi gözükse de, uzmanlar için bu niteliksel fark heyecan verici. Aaronson’un bloğuna bir okur, “Bu sonucun geçerli olduğunu varsayarsak, teorik bilgisayar biliminin çok kıymetli bir yapıtaşı olabilir ve buna tanıklık etmek büyüleyici bir şey” mesajını bıraktı.
Bugünlerde networkler (ağlar) ve grafikler baktığımız her yerde olsa da, ironik bir biçimde bu yeni algoritma bu kadar geniş bir uygulama alanı bulamayabilir. Bunun nedeni, izomorfik graf problemindeki birçok grafiğin şu andaki algoritmalar ile zaten çözülebilmesi. Aaronson, eğer yeni algoritma çalışırsa, şu anki algoritmalar ile çözülemeyen durumları çözmeyi başaracaklarını belirtiyor. Ayrıca yeni algoritma karmaşıklık teorisindeki en zorlu soruya, “NP” sınıfının gerçekten “P” sınıfından farklı olup olmadığı sorusuna cevap vermiyor. Araştırmacılar genelde “NP” ve “P” sınıfının birbirlerinden farklı olduklarını düşünüyor ve yanılırlarsa birçok şey, örneğin internet şifreleme teknikleri, inanılmaz bir şekilde zarar görebilir. Fakat henüz “NP” sınıfının “P” sınıfına eşit olmadığını gösteren bir kanıt yok.
Aaronson: “Yeni algoritmadaki asıl ilerleme zor kategorideki -NP- ana problemi, kolay kategoriye -P- indirgemesi. İzomorfik graf problemi tuhaf bir olguydu, zor olduğunu düşünüyorduk, ama yine de belli teorik özelliklerle daha kolay problemlerle de ilişkilendirebileceğimizi biliyorduk. Bundan sonra problem bu kadar zor olmayabilir.”
Elbette diğer araştırmacılar da Babai’nin çalışmasını incelemek zorunda. Aaronson, hâlâ çalışmanın detaylarının incelenmesi gerektiğini, Babai statüsündeki bir kimsenin bile hata yapabileceğini belirtiyor.
Çeviren: Semih Suçağlar
Yeditepe Üniversitesi Bilişsel Bilimleri Yüksek Lisans Programı
Kaynak: Adrian Cho, “Mathematician claims breakthrough in complexity theory”, http://news.sciencemag.org/math/2015/11/mathematician-claims-breakthrough-complexity-theory
