Bu yazıda neredeyse yarım asırdır matematikçileri uğraştıran “P ile NP eşit mi?” sorusundan söz edeceğiz. Bakalım nice Hesaplama Karmaşıklığı kuramcısına hayatı zehir eden neymiş.
Karmaşıklık kuramcıları bilgi işlem problemlerini doğal zorluklarına göre sınıflandırmaya çalışırlar. Bir problemin zorluğu, sorunun boyu (yani onu yazmak için kullandığımız harf sayısı) büyüdükçe cevabı bulmak için atılması gereken adım sayısının artma hızıyla ölçülür.
Tabii ki uzun soruları yanıtlamak kısa olanlara oranla daha uzun sürecektir, ama soru uzadıkça çözüm zamanının ne kadar uzadığı problemden probleme değişir. Bu fark karmaşıklık kuramının temel ayrımının tanımına yansır: “Polinom sınırlı” olan ve olmayan artışlar.
Polinom sınırlı artış
Teknik detaylardan arınmış yaklaşık bir tanım vereyim: Belirli bir problem için “polinom sınırlı zamanlı” bir çözüm yönteminiz varsa, şöyle bir K katsayısının da var olduğuna emin olabilirsiniz: Eğer soruların boylarını iki katına çıkarırsanız çözüm için atılması gereken adımların sayısı taş çatlasa K katına çıkar. Yani sorular uzadıkça yanıtların gelme süresi de artar, ama “çılgınca” artmaz; artış hızının “makul” kabul edilen bir sınırı vardır. Karmaşıklık kuramcıları bu özelliğe sahip çözüm yöntemleri olan problemleri “kolay”, olmayanları da “zor” kabul eder, çünkü eğer yönteminizin çalışma zamanı polinom sınırlı değilse çok kısa olanlar dışındaki soruları yanıtlamak yıllar, hatta asırlar alabilir, kimsenin de o kadar vakti yoktur.
Bu anlamda kolay problemlerin oluşturduğu kümeye “P” adı verilir. Bir önemli ayrıntı: Burada söz konusu olan çözüm yöntemlerinin (para veya zar atıp çıkan sonuca göre davranmak gibi) olasılıksal adımlar içermediğini ve klasik fizikte olmayan (bir cismin aynı anda iki farklı yerde olabilmesi gibi) kuantum özelliklerini kullanmadıklarını varsayıyoruz. Bu varsayımlar yapılmadığında işler değişebilir.
Kolay işler
Karmaşıklık kuramcıları onlarca yıldır bu “kolay problemler kümesi” P’nin sınırlarını saptamaya çalışıyorlar. İlkokulda öğrendiğimiz yöntemlerin hızlılığı sayesinde o dört ünlü aritmetik işlem hesabının P’nin içinde olduğunu biliyoruz. Bize bir ülkenin karayolları trafik haritasındaki yol uzunluğu bilgileri verildiğinde istenen iki şehir arasındaki en kısa yolu bulma problemi de P’de. Verilen iki sayının en küçük ortak katını bulma problemi de. Verilen bir sayının asal olup olmadığını saptama problemi de. Liste uzun, bu da güzel, çünkü pratikte makul uzunluklardaki sorularını kesinkes hatasız çözebileceğimiz problem aileleri sadece P’nin kapsadıkları.
Başkasının çözümünü kontrol etmek
Diyelim ki size bir ülkedeki tüm şehirlerarası otobüs hatlarının fiyat bilgileri ve belli bir miktar para verildi. Otobüslerin uğradığı tüm şehirlerden geçen bir tur yapmaya bütçeniz yeter mi yetmez mi? Bu ünlü "seyyar satıcı” problemidir. Bu problemi kolayca çözebilmeyi kim istemez? (Seyyar satıcıların isteyeceği kesin!) Ne yazık ki, onca yıldır üzerinde çalışan nice parlak beyin, seyyar satıcı probleminin P’nin içinde olup olmadığını bir türlü anlayamamıştır. Ne bu problem için polinom sınırlı zamanlı bir çözüm yöntemi bulunabilmiş, ne de böyle hızlı bir yöntemin var olmadığı gösterilebilmiştir.
Ama seyyar satıcı probleminin her problemde olmayan ilginç bir özelliği var. Tamam, bütçemize uygun bir tur olup olmadığını kısa sürede bulamıyoruz ama aniden karşımıza çıkan gizemli bir yabancı kendisinin bu ülkeyi avucunun içi gibi bildiğini ve elimizdeki parayla böyle bir gezinin yapılabileceğini iddia ederse ona körü körüne güvenmeden iddiasını kendi kısıtlı zamanımız içinde sınayabiliriz: Ona şehirleri hangi sırayla gezeceğimizi sorarız, sonra da yanıtının gerçekten bütçemizle otobüs hatlarına uygun ve hiç bir şehri dışarıda bırakmayan bir liste olup olmadığını kendi imkanlarımızla kontrol ederiz. Bu kontrol polinom sınırlı zamanda yapılabilir.
Bu türden, bir başkasınca çözüm olduğu iddia edilen kısa bir metnin sınanmasını kendimizin hızla yapabildiğimiz problemlerin kümesine karmaşıklık kuramında “NP” adı verilir.
Bir milyon dolar
21.yüzyılın başında Clay Matematik Enstitüsü, yeni asrın matematikçilerine meydan okuyarak 7 çözülememiş matematik bilmecesinin “başına ödül koydu”. Cevabını bulana enstitüce bir milyon ABD doları vaat edilen bu 7 sorudan biri de “P ile NP eşit midir?” sorusudur. Seyyar satıcı problemi için polinom sınırlı zamanda çalışan bir yöntemin var olmadığını ispatlayabilirseniz NP kümesinin P kümesinde olmayan bir eleman içerdiğini, yani eşit olmadıklarını göstermiş olursunuz, bir milyon da sizin olur. İşin ilginci, eğer seyyar satıcı problemi için hızlı bir yöntem bulursanız da soruyu çözmüş olursunuz, çünkü 1970’lerden beri biliyoruz ki bu problem için hızlı bir çözüm yöntemi otomatik olarak NP’nin içindeki tüm diğer problemleri de hızla çözecek yöntemlere tercüme edilebiliyor, ve böyle bir durumda P ile NP’nin eşit olduğu sonucu çıkıyor.
Aradan geçen sürede Clay sorularından sadece biri çözüldü: Rus matematikçi Grigori Perelman (solda) 2003’te “Poincaré sanısı” denen topoloji sorusunu (ilk soruluşunun üzerinden 99 yıl geçtikten sonra) yanıtladı. Ama Perelman kimi diğer matematikçilere olan kırgınlığını gerekçe göstererek hem Clay’in vereceği bir milyonu, hem de bu başarısından ötürü kendisine verilmek istenen diğer ödülleri reddedip evine kapandı. Matematiği bıraktığı söyleniyor. “P ile NP eşit midir?” sorusu hâlâ yanıt bekliyor, ama gördüğünüz gibi bu bir milyon dolar kazanmak uğruna girişilemeyecek kadar zor bir iş. Ayrı bir aşk istiyor.
Cem Say / Twitter: @say_cem