Bilimi severim. Hem de çok. Tüm bilim dalları doğanın bir yanının bilmecelerini çözmeye çalışır. Hepsi birbirinden güzeldir. Ama biri var ki sonsuz sayıda problemle uğraşıp onları birbirleriyle boy ölçüştürmeye çabalar, işte o en şahanesidir!
Herhalde tahmin ettiniz. Kendi araştırma alanımdan söz edeceğim bu yazıda: Hesaplama Karmaşıklığı’ndan yani.
Problem nedir?
Yukarıda “problem” derken kastım şuydu: Sadece bir doğru cevabı olan sorular vardır. “17’ye 43 eklersek kaç eder?” mesela. (Cevap “60”.) Bu soruyu hesap makinesinden kopya çekmeden yanıtlamak için kullandığınız yöntemi (ben ilkokulda öğrendiğim yöntemi kullandım) aynı türden sonsuz sayıda başka soruyu (“6555’e 13 eklersek kaç eder?”, “484757’ye 864 eklersek kaç eder?”, vs.) yanıtlamak için kullanabilirsiniz. İşte bu soru ailesine “toplama problemi”, onlardan herhangi birini çözmek için kullandığımız ortak yönteme de “toplama algoritması” diyoruz.
Eminim çarpma problemi için ilkokulda öğretilen algoritmayı da hatırlıyorsunuzdur. Ama problemler sadece aritmetikle sınırlı değil. Verilen bir isim listesinin alfabetik sıralanmış halini üretmek de bir problem, bir harita ve iki şehir adı alıp aralarındaki en kısa yolun hangisi olduğunu saptamak da. Örnekler saymakla bitmez.
Zorluk nasıl ölçülür?
Bu şekilde tanımlanan iki problemi birbirleriyle nasıl karşılaştırabiliriz? Mesela toplama mı daha zordur yoksa çarpma mı?
Kuşkusuz “3 çarpı 4” işlemi göze “659476869 artı 7585842” işleminden çok daha kolay görünüyor, ama unutmayın, “problem” derken bu tekil soruları değil, sonsuz sayıda soru içeren kümeleri kastediyoruz.
İki algoritma arasında adil bir karşılaştırma yapabilmek için ikisine de aynı “boy”da sorular verildiğinde cevaplamak için ne kadar zaman harcadıklarına bakılır. Sözgelimi rastgele seçtiğiniz 10’ar rakamlı iki sayı alın ve bunları bir kağıtta ilkokul yöntemiyle toplayın, başka bir kağıtta da çarpın. Aynı boydaki sorular için çarpma algoritmasının toplama algoritmasından daha uzun zaman aldığını gördünüz mü?
Ama bir detayı gözden kaçırmayalım. Bu örnek sadece ilkokulda öğrendiğimiz o çarpma yönteminin toplamanınkinden daha uzun zaman aldığını gösteriyor. Bu “çarpma problemi toplama probleminden zordur” demekle aynı şey değil. Ya ilkokuldakinden çok daha verimli, mesela iki sayıyı alt alta yazıp üçüncü satırda da çarpımlarını hızlıca hesaplamanıza el veren bir çarpma yöntemi varsa da biz bilmiyorsak? Kendi cehaletimizden ötürü çarpma problemini suçlamanın alemi var mı?
Moskova, 1960
Profesör Kolmogorov içeri girdi. Salondakiler heyecanla kıpırdandılar. Sovyetler Birliği’nin en büyük matematikçisinin bu yeni seminer serisine katılabilmek büyük şanstı. Kolmogorov ilk seminerde ilkokul çarpmasından söz etmeye başlayınca biraz şaşırdılar ama.
Batı kaynaklarında kimi zaman es geçilse de, Andrey Kolmogorov’un diğer pek çok konunun yanısıra Hesaplama Karmaşıklığı Kuramı’nın da öncülerinden olduğu kesindir. Kolmogorov binlerce yıldır daha hızlısının bulunamamış olmasından etkilenerek ilkokul yönteminin mümkün olan en hızlı çarpma algoritması olduğunu düşünüyor, ama bunu bir teorem olarak kanıtlayamıyordu. Seminerde de bu düşüncesini anlattı.
İzleyiciler arasındaki 23 yaşındaki matematik öğrencisi Anatoli Karatsuba tam bir hafta sonra, ikinci seminerinin ardından Kolmogorov’un yanına gidip “Profesör” dedi, “daha hızlı bir çarpma algoritması keşfettim!”
Daha iyisi var mı?
Karatsuba'nın binlerce yıldır kilitli duran kapıyı açmasından sonraki yıllarda matematikçiler boş durmadı. Ardarda, giderek daha uzun sayıların çarpımında öncekilere üstün gelen yeni çarpma algoritmaları keşfedildi. Rekor şimdilik Martin Fürer’in 2007’de duyurduğu yöntemde. Fürer algoritması neredeyse verilen sayıların boyuna doğru orantılı sürede çalışıyor, ama yine de tastamam doğru orantıyla çalışan ilkokul tarzı toplama algoritmasının eline su dökemiyor. Acaba bir gün toplama kadar hızlı çarpma yapabilecek miyiz? Yoksa çarpma problemi gerçekten de toplamadan daha mı zor? Henüz kimse bilmiyor.
Öğrencilerimle ben de Karmaşıklık Kuramı’nın balta girmemiş ormanlarında bir şeyler keşfetmeye çalışıyoruz. Neler mi bulduk? Artık o da başka yazılara.
Cem Say