P=NP ve Matematik Muhabbetleri

Dikkat! Bu yazı benim için tamamen deneysel bir nitelik taşıyor. İçeriği biraz sabır, biraz yürek ve matematik merakı istiyor. İnsanlığın entelektüel birikiminin en uç noktası sayılabilecek matematiğin en büyük problemlerinden biri hakkındaki son haftalarda yaşanan gelişmeleri hiçbir Türkçe kaynakta görmemek ve bu konuda yazmamak bana rahatsızlık veriyordu; bu fırsatla rahatlama fırsatı buldum. İyi okumalar!

Gazetelerde ya da haberlerde hatta birçok popüler bilim dergisinde dahi matematik veya matematikçilerin üzerinde uğraştıkları konular hakkında birşeylere rastlamak gerçekten zor. İnsanlar arasında ilkokul sıralarından kalmış bir matematik korkusunun yanında, matematikçiler hakkında saçları başları dağınık, soyut alemlerde gezen varlıklar olmaları ve çalıştıkları konuların da pek kolay anlaşılamayacağı önyargısı var. Belki de en ilginç ve çarpıcı olanı ise fizik, kimya, genetik gibi fazla ön planda olmadığından, 21. yüzyıla gelmişken hala matematikte çözülmemiş büyük problemler olmasının algılanma zorluğu matematiği toplum içerisinde pek de “popüler” kılmıyor.

Tüm bu saydığım benzer nedenleri göz önüne alarak 2000 yılında, yeni milenyumun eşiğinde matematik alanının halen aktif ve içinde birçok heyecan verici zor problemi barındırdığını ispat edercesine Amerika tabanlı Clay Matematik Enstitüsü 7 problem yayınladı ve her çözüm için de 1’er milyon dolar ödül koydu. Bu yayınlanan problemler ilk akla gelebilecek şekilde bir grup matematikçinin bir odaya kapanıp hazırladıkları sorular değil elbette; çoğu onlarca yıldır birçok matematikçinin uğraşıp sonucuna yaklaşamadığı türden ve hepsinden önemlisi problemlere herhangi bir çözüm önerilmesi durumunda o alanda devrimsel denebilecek ilerlemeye neden olabilecek türden.

Bahsi geçen 7 problemden Poincare savı, 2003 yılında Rus bir matematikçi(Girigori Perelman) tarafından çözüldü. Çözümünün karşılığı olarak Matematik dünyasının Nobel’i Fields Madalyasını ve en ilginci Clay Enstitüsü’nun 1 milyon dolarını kabul etmeyince haliyle medya adamı “kaçık,çatlak vb” sıfatlarıyla afişe etti. Bu konuyu güzel bir dille anlatıldığı Prensese Mektuplar blogundan okuyabilirsiniz. Benim bahsetmek istediğim ise farklı bir problem. Geçen haftalarda çözüldüğü öne sürülen, kanıt üzerinde çalışan uzmanlar tarafından ise “ciddi eksiklerin” olduğu iddia edilen fakat tam bir sonuca varılamayan P=NP problemi…



Problemin ismi konuya yabancı olanlara hiçbirşey ifade etmeyebilir ama formüle edildiği haliyle P=NP problemi teorik bilgisayar bilimi ve matematikte önde gelen çözüm bekleyen problemlerden birisi. Bilgisayar biliminde “karmaşıklık teorisi” olarak çevrilebilecek çalışma alanında formüle edildiği 1971 yılından beri çözüm bekliyor. Kısaca tanımlamak gerekirse P=NP, problemlerin çözümünün kolaylık dereceleriyle ilgili bir problem; yani problemlerin kendisi hakkında bir problem.
Birkaç örnek verip ufak detaylara girmeden önce birkaç tanım yaparak başlayalım. Öncelikle elimizde bir problem var buna hızlı bir çözüm yöntemi arıyoruz. Öne sürdüğümüz problemin çözümüne ulaşmak için ortaya koyduğumuz adım adım işlemlere “algoritma” diyoruz ve bu algoritmamız ne kadar az adımdan oluşursa bizim için o kadar iyi, çünkü bu algoritmayı çalıştırmak için kullanacağımız bilgisayarın kaynaklarını(hafıza ve işlemci) o derece az kullanacağız. Farklı problemler için farklı algoritmalar kullanıyoruz ve bu algoritmaların bazıları çok verimli ve hızlı iken bazıları çok verimsizler ve çalışmları yüzlerce yıl olabiliyor. Yani öyle problemler var ki çözümleri (önerilen algoritmalarla) kolay hesaplanabilirken, bir diğer problemler var ki çözümleri için verimli bir algoritma önerilemiyor. En iyisi örnekle açıklamak:

Elimizde basit işlemler (toplama,çıkarma, çarpma) yapan bir bilgisayarımız var. Bu bilgisayara her biri n basamaklı iki tane sayı giriyoruz ve toplamasını istiyoruz. Bilgisayarımızın toplama işlemi için tanımlanmış bir algoritması var ve her bir basamağı toplayıp eldeleri de hesaplayarak bize bir sonuç gösteriyor. Bilgisayara toplam 2n basamaklı bir giriş yaptığımızdan dolayı ( her bir sayı için n basamak) sonucu 2n adımdan hesaplayacağını ön görüyoruz. Bir başka örnek olarak iki tane n basamklı sayının çarpımını örnek gösterebiliriz. Bu sayıların her bir basamaığını birbiriyle çarpıp eldeleri hesaplayacağı için çarpımları \(n^2\) , eldeleri de \(n\) adımda, toplamda \(n^2 + n\) basamakta işlemi tamamlarız. Benzer şekilde \(n\) girdiye karşılık \(An^k\) ( A ve k birer sabit) adımdan sonuç döndüren algoritmalara verimli (efficient) algoritmalar diyoruz ve verimli algoritma çözümleri olan problemlere de polinom zamanda çözümü olan problemler ya da kısaca P diyoruz.

Diğer bir problem türünü ise \(n^2\), \({3n}^5\) gibi polinom zamanda çözümden ziyade çözüm zamanı ve adım sayısı çok daha hızla büyüyen \(2^n\) , \(5^n\) ya da \(n^n\) gibi üslü zamanlarda(exponential time) çözümü olan problemler oluşturuyor. Bunlara örnek olarak seçim problemlerini örnek gösterebiliriz. Örneğin 200 kişilik arkadaş grubunuzun içerisinden belirli özelliklere göre 100 kişiyi bir partiye davet edeceksiniz. 200 kişi içinden kaç tane 100 kişilk seçim yapabileceğinizi söyleyim : \(9,0548 \times 10^{58}\) . Bu sayı inanılmaz büyük bir sayı ve her nanosaniyede 1 işlem yapabilen bir bilgisayarla dahi \(10^{50}\) ( 10’un yanında 50 sıfır) yıla yakın bir sürede ancak hesaplayabiliriz. Bu problemde, 200 kişi içinden 100 kişiyi seçme olarak söyleyebileceğimiz problemimizi 200’ün 100’lü kombinasyonları olarak ifade edebiliriz bunun yaklaşık olarak \(4^{100}\) ile orantılı olduğunu söyleyebilirim (Detayları merak edenler için sonuç Stirling formülü ile elde edilebilir). Görüldüğü gibi burda girdimiz olan 100’ün bir kuvveti değil, 100’ü üs olarak alan bir zaman ifadesi var(\(4^n\)).Bu problemlere de zor problemler ya da N diyoruz.

Bu paragrafa kadar gelenleri öncelikle saygıyla selamlayarak devam ediyorum :) P ve N’nin yanında bir de NP olarak adlandırılan problemler var ki bu problemlerin çözümlerinin muhtemelen N problemlerle aynı sınıfta olduğu düşünülmesine rağmen (yani exponential time), olası bir çözüm verildiğinde çözümün verimli bir çözüm olup olmadığını sınamak bir P problemi kadar kolay. Bu problemlere örnek olarak da ünlü gezgin satıcı problemini(Travelling Salesman) ve harita renklendirme problemini verebiliriz.

Şimdi 1 milyon dolarlık sorunun can alıcı kısmına gelirsek; soru diyor ki çözümü verimli bir şekilde sınanabilen problemlerin(yani NP’ler) aynı şekilde verimli bir çözümleri bulunabilir mi(yani P olabilirler mi?) Yani NP problemleri aslında birer P problemi mi? Çoğu kişi bunun böyle olmadığını düşünüyor fakat halen kanıtlanmış değil. Geçen hafta HP Labaratuar’larından Vinay Deololikar adlı bir araştırmacı internette yayınladığı 100 sayfanın üzerinde bir kanıt ile NP’nin P’ye eşit olmadığını iddia etti. Birçok matematik profesörü (aynı zamanda aktif blog yazarı) hemen probleme el attı ve bir hafta kadar süren bir aktif tartışmanın ardından kanıtta birkaç “ciddi sorun” tespit ettiler. Sorunlar olsa da konuyla ilgilenen herkes Deololikar’ın bakış açısının soruya yeni bir perspektif kazandırdığı konusunda hem fikir. Tartışma halen sürüyor ve sonucu merakla bekliyoruz.

Peki son olarak bunca teorik tartışmanın ardından “modern anlayışımız” gereği konunun pratikte neler getirip getirmeyeceği üzerine de birkaç şey söylemeden olmaz. NP, P’ye eşit olsa nolur olmasa nolur diyorsanız o kadar hafife almayın derim çünkü bu problemin olumlu yönnde çözümü (yani P=NP) bütün internet güvenliğini altüst edebilir. Şöyle ki, günümüzde internet ş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 vay halimize :) Tabi çözümün bu yönde olması interneti yerle bir ederken günlük yaşamamızda ve ekonomide inanılmaz verimliliğe yol açacak çözümlerin de kapısını açacak.

Her ne kadar çoğu bilgisayar bilimci ve matematikçi ne internetin çökeceğini ne de "büyük verimlilik çağının" başlayacağını düşünmese de artık günümüzde her türlü hesaplamanın bilgisayarlarla gerçekleştiriliyor olması ve gün geçtikçe daha da karaşık ve zor sorularla uğraşıyor olmamız P=NP probleminin çözümünün hesaplama alanında büyük bir çığır açacağının sinyallerini veriyor.

Bu yazıda bütün bunları tartışıp üstüne 2010 Matematik Fields Madalya’sını alan matematikçiler ve çalışmaları üzerine de konuşmak istiyordum ama bir sonrakiyazıya erteleyim en iyisi. Sıkılarak ya da sıkılmadan okuyan okuyuculardan yazının içeriği ve sunuş şekliyle ilgili ufak bir yorum istesem çok şey istemiş olmam değil mi ? ;)
P=NP konusunda bu yazı kesmedi diyorsanız size önerebileceğim harika kaynaklar:

• Mathematics : The New Golden Age , Keith Devlin : “Hilbert’s Tenth Problem”(Chapter 6) ve “The Efficiency of Algorithms”(Chater 11)
• Bir Sayı Tut, Malcolm E. Lines – Tübitak Yayınları : "NP Problemi Nedir” (12. Bölüm)
• From Here to Infinity(Problems of Mathematics) , Ian Stewart : “Digix Algorizmi"(Chapter 21) ve “The Limits of Computability” (Chapter 21)
• Status of the P versus NP Problem ( Problemin özeti ve çözüm girişimlerinin tarihine dair muhteşem bir yazı)
• A Tale of A Serious Attempt At P≠NP ( Geçen hafta önerilen kanıtın ve incelenme sürecinin harika bir özeti )
• How can Maths can make you rich and famous? (Milenyum problemleri ve P=NP probleminin detaylarına dair Plus dergisinin güzel bir yazısı)