2 Eylül 2010 Perşembe

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:

19 yorum:

D. dedi ki...

"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 ? ;)"

Ben gayet ilgiyle okudum ve cok guzel bir yazi olmus. Eline saglik.

Arif Bayırlı dedi ki...

Yorum için teşekkürler! Yazıyı okuyan 50'nin üzerinde kişiden sadece yorum yapan sizsiniz (şimdilik :) ) Beğenip, faydalandığınıza sevindim!

Selçuk AK dedi ki...

Çok Güzel bir yazı elinize sağlık.
Çok açık ve anlaşılır.Bir mat. öğrt mezunu olarak bu kadar karışık bir olay ancak bu kadar güzel anlatılır.

Recep Erden dedi ki...

Böyle zor bir konuyu çok açıklayıcı anlatmışsın tebrikler!

Tanrıya sorulacak bi soru daha öğrendim

Adsız dedi ki...

Çok güzel bir yazı olmuş. Gerçekten anlaşılması zor bir konuyu gayet açık bir şekilde anlatmışsınız. Teşekkürler

Adsız dedi ki...

Yazıyı yazıldığı tarihten 2 yıl 2 gün kadarcık sonra okusam da yazıyı anlayabildiğime göre çok açıklayıcı ve öz bir anlatım olmuş :) Numb3rs adlı bir dizide bahsedildiği için araştırdım, oldukça ilginç bir problem, çözülmesini dört gözle bekliyorum. ( Çözümü anlayacağımdan değil, eşit mi değil mi onu merak ediyorum :D

Arif Bayırlı dedi ki...

Yorumlar için çok teşekkürler. Yazıdaki sayısal ifadeler için kullandığım LaTeX scriptindeki problemi çözdüm; görünmeyen sayı fontları şu anda görülüyorlar..

Bu konuya dair Türkçe kaynaklarda dişe dokunur bir yazı bulamadığım için karalamıştım bu yazıyı ama istatistiklere baktığımda blogun en çok okunan yazıları arasında; bu benim için çok sevindirici!

Problemin çözüm olasılığına dair ilginç bir yazı ile güncelleme yapayım istedim bir de.. Scott Aeronson'ın SciAm'de yayınladığı kuantum bilgisayarların limitleri ve NP problemleri çözme kapasiteleri üzerine: http://bit.ly/Thc3ac

Adsız dedi ki...

Zor bir konuya, böylesine anlaşılır bır anlatım getirmişsiniz. Tebrik ediyorum. Kabul ederseniz bir konuda geliştirme talebim olacak. NP konusunda daha açıklayıcı olabilirsiniz mesela. NP'nin P ile ifadesine ilişkin bazı örnekler vermek faydalı olabilir diye düşünüyorum. P=NP eşitliği nasıl ifade edilebiliyor? Tekrar elinize sağlık.

Unknown dedi ki...

Elinize sağlık. Sözel bilgi de olsa ilgi çekici. Keşke aynı cesareti konunun uzmanı (sözde) matematikçilerimizde böyle rahat yazabilseler...

ferhat dedi ki...

Güzel güzel, ben sıkılmadım hatta devamı vardır diye merak ede ede okudum.

nSabri dedi ki...

Elinize sağlık.Yıllar geçse bile eskimeyen bir blog yazınız olmuş:)ilgiyle okudum teşekkür ederim:)

Arif Bayırlı dedi ki...

Çok teşekkürler olumlu yorumlar için! Epey uzun zaman önce yazdığım bir yazının hala okunuyor olması sevindirici!

Adsız dedi ki...

bilgi kaybolmaz 50 yıl sonrada bu yazıyı okuyup tşk edecek ınsanlar olacaktır 7 yıl sonra okuyup tşk ettiğim gibi...

Adsız dedi ki...

hesaplama teorileri dersi ile iligi araştırma yaparken rastladım yazınıza, çok sade ve anlaşılır anlatmışsınız.
teşekkürler

Unknown dedi ki...

İngilizce endüstri mühendisliği okuyorum ve "ağ akışları ve tam sayılı programlama" dersinde gördüğümüz bir konu ama hocamız çok ayrıntılı anlatmadı daha.
Ingilizce kaynaklardan da okudum bu konuyu ama sizin anlatımınızla çok daha iyi anladım.
Teşekkür ederim bu yazı için

Unknown dedi ki...

10 yıl olmuş ve gayet açık anlatılmış teşekkürler

Unknown dedi ki...

Soruyu ilk kez burada anladım.

Ali Akay dedi ki...

Bir kaç kaynaktan okudum, en anlaşılır şekilde olan senin yazıydı, tebrikler :)

Unknown dedi ki...

Açıklayıcı olmuş, teşekkürler.

Paylaş!

 

Copyright © 2010 Gök Günce | Blogger Templates by Splashy Templates | Free PSD Design by Amuki