P, NP ve P-NP arasındaki bağ…

P harfi “polynomial”, NP harfleri ise “non-deterministic polynomial” ifadelerini temsil eder, Türkçe karşılıkları “polinom” ve “belirleyici olmayan polinom”dur. “P eşittir NP?” ise Hesaplama Teorisi’nin en temel ve meşhur problemidir.

NP, belirsiz Turing Makinesi ile çokterimli (polinomsal) zamanda çözülebilen karar problemlerini içeren karmaşıklık sınıfıdır. Bu sınıftaki problemler belirli Turing Makinesi ile çokterimli zamanda doğrulanabilirler ve bu şekilde doğrulanabilen her problem NP sınıfındadır. Bu nedenle NP, (belirli Turing Makinesi ile) çokterimli zamanda doğrulanabilen problemlerin sınıfı olarak da tanımlanabilir. Belirli Turing makinesi aynı zamanda belirsiz Turing makinesi olduğundan, P sınıfındaki bütün problemler aynı zamanda NP’dedir.

Melekimsi(şanslı seçim) belirlenimsiz bir Turing makinasıyla polinomsal zamanda çözülebilen problemler NP kümesini oluşturur. Belirlenimsiz makina, belirlenimli bir Turing makinası ile simüle edilebileceği için belirlenimsiz makinanın çözebildiği problemler kümesi, belirlenimli makinanın çözebildiği problemler kümesine eşittir.

Polinomsal zamanda çözülen problemler

Hesaplama teorisinde, bazı tip problemlerin çözümü için en etkili algoritmaların çalışma süresinin girilen verinin büyüklüğüne bir polinom cinsinden bağlı olduğu bilinmektedir (buna polinomsal zamanda çalışan algoritma adı verilir), bu tür problemler P kategorisindeki problemlerdir. Mesela verilen n basamaklı bir sayının asal olup olmadığını kontrol etmek için çalışma süresi n^6 mertebesinde bir polinomla hesaplanabilen bir algoritma vardır. Dolayısıyla verilen bir sayının asal olup olmadığının araştırılması P kategorisinde bir problemdir.

Polinomsal zamanda çözülemeyen problemler

Buna karşılık bir diğer grup problem vardır ki bunlar için sorulan soruya girilen verinin büyüklüğüne polinom mertebesinde bağımlı bir sürede cevap verecek bir algoritma bilinmemektedir. Fakat bu tür bazı problemler için eğer bir şekilde cevabı tahmin edebiliyorsak, tahminimizin doğruluğunu sınamak için veri büyüklüğüne polinom mertebesinde bağımlı sürelerde çalışacak algoritmalar vardır. Bu tür problemler, yani bir tahminin doğruluğunun kontrolü için çalışma süresi verinin büyüklüğüne polinom cinsinden bağımlı bir algoritma olan problemler de NP kategorisini oluştururlar. Örnek olarak verilen n basamaklı bir sayının asal çarpanlarının neler olduğu sorusunu düşünebiliriz. Bu sorunun cevabı için bilinen en iyi algoritmanın çalışma süresi n sayısına bir polinom cinsinden değil de eksponansiyel fonksiyonlar cinsinden (e^n misali) bağımlıdır (buna üstel zamanda çalışan algoritma denir), fakat bu problem için eğer bir şekilde cevabı tahmin edebiliyorsak tahminimizin doğruluğunu sınamak için n sayısına polinom mertebesinde bağımlı bir sürede çalışacak bir algoritma mevcuttur. Dolayısıyla verilen bir n basamaklı sayının asal çarpanlarının neler olduğu sorusu NP kategorisindedir.

P ve NP arasındaki bağ

Bu iki kategoriden NP’nin P’yi içerdiğini görmek kolaydır. Eğer bir sorunun cevabını verinin büyüklüğüne polinom mertebesinde bağımlı sürede çalışacak bir algoritmayla bulabiliyorsak, bu soruya cevap olarak üretilmiş bir tahminin doğruluğunu da verinin büyüklüğüne polinom mertebesinde bağımlı sürede çalışacak bir algoritmayla kontrol edebiliriz. Bunun için verilen sorunun cevabını verecek algoritmayı çalıştırıp, onun verdiği cevabı kendi tahminimizle karşılaştırmak yeterlidir. “P=NP?” problemi bunun tersinin de doğru olup olmadığını sorar. Yani NP kategorisinde olup da P kategorisinde olmayan problemler var mıdır? Veya diğer bir dille asal çarpanların bulunması için polinom mertebesinde bir sürede çalışacak bir algoritma gerçekten yok mu yoksa var da biz mi bulamıyoruz? Bu alanın uzmanlarının çoğunun görüşü bu tür algoritmaların gerçekten de var olmadıkları için bulunamadığı (yani P nin NP’ye eşit olmadığı) şeklinde ancak bu soruya kesin bir cevap verilebilmesi şimdilik çok zor gözüküyor.