Nedir bu P=NP Problemi, Yoksa Çözüldü mü?

Texas Üniversitesi’nde Bilgisayar Bilimleri profesörü tarafından bugün yayımlanan yeni bir makale RP=NP eşitliğini öne sürüyor. Yazımızın devamına geçmeden ve P=NP problemini irdelemeden önce spoiler verelim. Böyle bir eşitliğin kesin olarak doğrulanması demek bütün internet güvenliğinin altüst edileceği, bütün kriptoloji sistemlerimizin çökmesi anlamına gelir.

Donald Knuth’un Basit (?) Problemi

Modern algoritmanın kurucusu sayabileceğimiz Donald Knuth bizlere bir soru soruyor. “1’den 50’ye kadar olan sayıların karekökleri iki kümeye ayrılsın ve bu iki kümedeki kareköklerin toplamları birbirine olabildiğince yakın olsun”

Basit bir soru gibi gözüküyor değil mi?

Sonuçta yapmamız gereken 50 sayının karekökünü almak ve onları iki kümeye ayırmak. 1’in karekökü olan 1’i bir kümeye dağıtırsak geri kalan sayıları iki kümeye 249 biçimde ayırabiliriz. Sonradan her kümenin arasındaki farkı bulur ve farkı en küçük olan kümeyi seçeriz.

Ama Donald Knuth’un bir isteği daha var: “Program en fazla 10 saniye içinde yanıt versin.”

İşte bu noktada takılıyoruz. Knuth’un sorusu göründüğü kadar basit değil, hatta çok çok zor ve özünde çok önemli başka bir problemi barındırıyor.

Problem Zorlukları

Karmaşıklık kuramcıları problemleri doğal zorluklarına göre sınıflandırmaya çalışırlar. Bir problemin zorluğu, sorunun boyu 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.

Yani sorular uzadıkça yanıtların gelme süresi de uzar ancak “çılgınca” bir düzeyde artmaz; artış hızının “makul” düzeyde olduğu kabul edilen bir sınır vardır. Karmaşıklık kuramcıları bu özelliğe sahip problemleri “Kolay” olmayanları ise “Zor” olarak sınıflandırıyorlar. Eğer yönteminizin çalışma zamanı polinomal sınırlı değilse çalışması asırlar alabilir ve kimsenin bir problemi çözmek için bu kadar zamanı yoktur.

Şifre Kırma Süresi

Bilgisayarlar onlara verdiğiniz algoritmadaki emir dizilerini yerine getirerek çalışır ve yazdığınız algoritmaya göre çalışması birkaç mikro saniye de alabilir birkaç yüzyıl da. Yani bir algoritma yazmanız ve onun düşük sayılarda hemen çalışması yazdığını algoritmanın güzel bir algoritma olduğu anlamına gelmez.

Sadece sayılardan oluşan 10 haneli bir şifreyi kırmak 40 saniye gibi bir süre alırken 18 haneli bir şifreyi kırmak 126 yıl alır. İşin içine harfler, semboller girdiğinde ise bu süre kentilyon yılları bulabilir. (Tablo-1)

Çözülemeyen Gezgin Seyyar Satıcı Problemi

Algoritma ile zaman arasındaki ilişkiyi anlatabildiysek bu konuyla alakalı bir diğer ünlü problem “Gezgin Seyyar Satıcı (Travelling Salesman)” problemini inceleyelim. Elinizde bir miktar para var ve bir ülkedeki tüm şehirleri en ucuz şekilde gezmek istiyorsunuz.

Ülkede A-B-C şehirlerinin olduğunu farz edersek A-B-C sırasının maliyeti 100TL, A-C-B sırasının maliyeti 90TL ise en karlı yol A-C-B sırası olacaktır ve o yolu tercih edersiniz. Şehir sayısı az olduğunda yazılan algoritmalarla bu problem çok hızlı bir şekilde çözülebiliyor. Ancak şehir sayısını 100’e çıkardığımızda ve elinizde saniyede 218 işlem yapacak bir bilgisayarınız olduğunda bu problemi çözmeniz 4000 yıl alacaktır.

Bilgisayar Biliminde Problem Sınıflar

P sınıfı yani “kolay” problemler olarak adlandırılan problem polinom zamanda çözülebilecek problemlerdir. Np sınıfı ise polinom zamanda doğrulanabilecek problemlerdir. P sınıfındaki her problem RP sınıfı içindedir ve NP sınıfı içindedir. (Tablo-2)

Çünkü polinom zamanda çözüm bulmak problemin aynı zamanda kendi kendisini doğrulamasıdır. Asıl soru şu: NP tipi problemler için polinom zamanda çözecek bir algoritma bulmak mümkün müdür?

Randomized Complexity Classes (Tablo-2)

Milyon Dolarlık Soru

Ne yazık ki, onca yıldır üzerinde çalışan nice parlak beyinler, 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. Clay Matematik Enstitüsü ise bu sorunun çözülebileceğini ya da çözülemeyeceğini ispatlayana kişiye yani P≠NP eşitsizliğini de P=NP eşitliğini ispatlayan kişiye 1 milyon dolar ödül verecektir.

Şimdiye kadar P≠NP eşitsizliği de P=NP eşitliği de gösterilememiştir. Ancak yeni yayınlanan bu makale bütün bildiklerimizi değiştirebilir!

Sonuç

Eşit olsa ne olur olmasa ne olur demeyin! Başta dediğimiz gibi bu eşitliğin gösterilmesi bütün internet güvenliğimizi alt üst edebilir. Sonuçta şifrelerimizin güvenliği çok büyük sayılarda asal çarpanlara ayırmanın imkânsız olmasından yani bu problemin NP olmasından kaynaklanıyor. Eğer NP=P eşitliği ispat edilirse ve bu probleme P’de bir çözüm bulunursa bütün güvenlik sistemleri çökebilir.

Andras Farago’nun RP=NP ispatına ise çok teknik ve uzun olduğu için değinemeyeceğiz. Eğer bu 59 sayfalık makaleyi incelemek isterseniz buradan inceleyebilirsiniz.

Bakalım bu ispata bilgisayar bilimcilerinin tepkisi ne olacak ve bu ispat doğrulanabilecek mi?

Kaynaklar:

  • https://en.wikipedia.org/wiki/RP_(complexity)
  • https://en.wikipedia.org/wiki/P_(complexity)
  • https://en.wikipedia.org/wiki/Travelling_salesman_problem
  • https://www.csie.ntu.edu.tw/~lyuu/complexity/2010/20101214.pd
(Visited 228 times, 1 visits today)

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir