P = NP? İkilemi

Bu ikilem bilgisayar bilimlerinin en entellektüel konularından birine ait. Doğru cevabını veremeyeceğim malesef, verebiliyor olsaydım şu an muhtemelen çok başka yerlerde olurdum 🙂 Ama şunu söyleyebiliriz ki çoğu uzman bu iki sınıfın eşit olmadığını düşünüyor. Peki tam olarak kanıtlanmış bir şey var mı? Hayır.

Yazı fotoğrafında gördüğünüz şey şaka değil, gerçekten 1.000.000 dolar ödülü var bu sorunun. Ayrıca eğer P=NP denklemi doğrulanırsa matematik kuramlarının kökünden sarsılacağı, bilgisayar bilimde şu an kullandığımız şifreleme tekniklerinin hiç bir öneminin kalmayacağı belirtiliyor. Biraz korkutucu 🙂

Şimdi biraz teorik bilgi verelim.

P sınıfı (ing . Polynomial) deterministik bir algoritma ile polinom zamanda(üstel zamanın altı) çözülebilen karar problemlerini (ing. decision problems) temsil ediyor. (Bu arada problemlerin normal hali bir dizi karar problemine indirgenebiliyor ve burada biz bunların karar versiyonlarını ele alıyoruz). Diğer bir deyişle eğer ilgili problemi polinom zamanda çözebilen bilinen en az bir deterministik algoritma varsa o problem P sınıfındadır diyebiliyoruz. Örneğin bir dizi sayıyı sıralama problemi P sınıfına aittir çünkü örneğin Birleştirmeli Sıralama (ing. Merge Sort) algortiması en kötü durumda (ing. worst case) bile bu işi polinom zamanda yapabilmektedir. (O(nlogn))

NP sınıfının (Dikkat ! NP sınıfı “non-polynomial” değil “nondeterministic polynomial” anlamındadır) tanımını vermeden önce, “nondeterministic polynomial algorithm” tanımını vermemiz gerekiyor. Bunun iki aşamalı soyut bir prosedürü var :

  • Problemi çözmek için rastgele sözde bir çözüm “string”i üretilir.
  • Bu çözümün doğru olup olmadığı polinom zamanında kontrol edilebilmelidir.

İşte NP sınıfı nondeterministic bir algoritma ile polinom zamanda çözülebilen karar problemlerinin sınıfıdır. Bir başka deyişle, bir problemin önerilen çözümleri polinom zamanında doğrulanabiliyorsa o problem NP sınıfına dahildir. Örneğin Gezgin Satıcı Problemi (ing. Traveling Salesman Problem) bu sınıftadır, çünkü herhangi bir çözüm (şehirlerin sırası) için bu çözümün örneğin belirli bir değerden küçük olup olmadığı polinom zamanda rahatlıkla bulunabilir. (Henüz GSP’yi çözen bilinen bir polinom zamanlı algoritma olmadığından bu problem P sınıfındadır diyemiyoruz.) Tabi P sınıfına ait olan tüm problemler bu mantıkla zaten çözülebileceğinden, NP sınıfının P sınıfını kapsadığını rahatlıkla söyleyebiliriz.

Böyle bir tanımla sanki tüm problemler NP’ye dahil olur, NP dışında bir problem olamaz gibi geliyor değil mi? Öyle değil. Örneğin “bir kümenin tüm alt kümelerini bulma problemi” NP içinde yer almıyor. Problem doğası gereği “combinatorial” bir yapıya sahip. n tane eleman için 2 üzeri n tane çıktı üretmek zorundasınız. Yani problem P sınıfında zaten değil. Ancak size verilen bir çözüm örneğini polinom zamanda kontrol de edemiyorsunuz doğru mu değil mi diye. Çünkü yine üstel sayıda eleman var dokunmanız gereken. Tabi bir de Turing’in “halting problem”i gibi herhangi bir algoritma ile çözülemeyen problemler de var. (bunlara “undecidable” problemler deniyor.)

Şimdi önemli noktaya geliyoruz. Ama önce “polinom zamanda indirgenebilir olma” (ing. polynomially reducible) tanımını yapmamız gerekiyor.

Bir karar problemi olan D1’in örneklerini yine bir karar problemi olan D2’nin örneklerine aşağıdaki şekilde dönüştüren bir ‘t’ fonksiyonu varsa, D1 problemi D2 problemine polinom zamanda indirgenebilir diye tabir edilir:

  • ‘t’ D1’in tüm evet örneklerini D2’nin evet örnekleri ile, D1’in tüm hayır örneklerini D2’nin hayır örnekleri ile eşleştirecek.
  • ‘t’ bir polinom zamanlı algoritma ile hesaplanabilir olacak.

“Polinom zamanda indirgenebilir olma” çok önemli çünkü bizi “NP-complete” sınıfının tanımına taşıyor.
Aşağıdaki durumlarda bir karar problemi D’nin NP-complete olduğu söylenir:

  • Problem NP sınıfına ait olacak,(yukarıda verdik tanımını)
  • NP’deki tüm problemler bu probleme polinom zamanda indirgenebilir olacak.

Ne? NP sınıfındaki tüm problemler mi? NP sınıfında binlerce problem olabilir, peki biz yeni bir problemin NP-complete olduğunu ispatlamak için NP sınıfındaki tüm bu binlerce problemin yeni problemimize polinom zamanda indirgenebilir olduğunu mu göstermek zorundayız?

Neyse ki hayır. Daha önceden zaten NP-complete olduğu bilinen bir problemin yeni problemimize polinom zamanda indirgenebilir olduğunu göstermemiz yeterli. Çünkü bu bilinen problem zaten NP-complete olduğu için, tanım gereği NP sınıfındaki diğer tüm problemler buna dönüştürülebiliyor. O zaman geçişkenlik (ing. transitivity) özelliğinden dolayı bizim yeni problemimize de dönüştürülebilir. Tabi bunun için ilk bir kök problem gerekiyor. Sağolsun Stephen Cook 1971 yılında “CNF-satisfiability” probleminin NP-complete olduğunu ispatlamış.

Bunun önemi ise şu : NP-complete olduğu bilinen sadece tek bir problem için bile polinom zamanlı bir algoritma bulunursa, NP’deki tüm problemlerin polinom zamanında çözülebilir olduğunu söyleyebiliriz. Çünkü tanıma göre NP’deki tüm problemler bizim problemimize indirgenebiliyor olur. Yani bu durumda P = NP’dir diyebiliiriz.

Yazının başında da belirttiğimiz gibi araştırmacıların çoğu P ile NP sınıflarının eşit olduğunu düşünmüyor. Ama denemeye değmez mi? NP-complete olduğu bilinen binlerce problemden sadece birine polinom zamanlı bir algoritma bulmanız yeter. Bu buluş sizi dünyaca ünlü yapabilir.

Son olarak bahsetmeden geçmeyelim, bir de NP-hard sınıfı var. Biraz “informal” bir tanımı var ve “en az NP sınıfındaki en zor problemler kadar zor.” problemleri temsil ediyor. Yani NP’nin bir kısmı ile, NP’de olmayan bazı problemleri kapsıyor. Yukarıda bahsi geçen “bir kümenin tüm alt kümelerini bulma problemi” NP’ye girmez ama NP-hard sınıfına girer.

Aşağıdaki şekilde şu ana kadar bahsettiğimiz sınıfların bir gösterimi var. Yalnız fark edeceksiniz ki bu şekil P ile NP sınıflarının aynı olmadığını varsayıyor. Eğer P=NP ise sanki bu şekil değişir gibi. Ne dersiniz? 🙂

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak.