P’ye karşı NP problemi henüz çözülemeyen Riemann hipotezi gibi çözülememiş bir milenyum problemidir. Milenyum problemleri 7 adet karmaşık matematik problemleridir ve şu ana kadar sadece Poincare hipotezi çözülebilmiştir. Milenyum problemleri Clay Matematik Enstitüsü tarafından 2000 yılında belirlenmiş olup her birinin ilk doğru çözümüne 1 milyon dolar ödül konulmuştur.
Zaman Karmaşıklığı
Öncelikle P ve NP’nin neye karşılık geldiğini anlayabilmek için biraz bilgisayar bilimlerinin temellerinden biri olan zaman karmaşıklığını anlamak gerekir. Zaman karmaşıklığı algoritmaların çalışma hızı hakkında bize bilgi verir. Bir algoritmanın verimini anlamak için algoritma analizi yapılır ve o algoritmanın zaman karmaşıklığı ve alan karmaşıklığı hakkında bilgi alınır. Zaman karmaşıklığı süre olarak ifade edilmez, algoritmaya gönderilen verinin doğrusal artışına bağlı olarak algoritmanın uyguladığı işlem sayısının artışının nasıl değiştiğini gösterir. Örneğin n elemanlı bir dizi gönderdiğimizde eleman sayısındaki her bir artışa karşılık algoritmanın yaptığı işlem sayısı n^2 ile paralel olarak artıyorsa problemin zaman karmaşıklığı O(n^2) olarak gösterilir ve bu gösterime Büyük O gösterimi denir. Zaman karmaşıklığı örnek vermek gerekirse; sabit, doğrusal fonksiyonlar olabileceği gibi üstel veya faktöriyel de olabilir. Uzun lafın kısası fonksiyonun artışı ne kadar fazlaysa bir algoritmanın zaman karmaşıklığı da o kadar fazladır.
Zaman Karmaşıklığı Sınıfları
Bilgisayar biliminde zaman karmaşıklıkları sınıflandırılmıştır ve bunlardan ikisi P ve NP’dir. P, polinomsal zamanı ifade eder. Polinomsal zamanda çalışabilen algoritmalar problemin teoride hızlı çözülebildiği kadar pratikte de hızlı çözülebileceğini ifade eder. NP ise belirleyici olmayan polinomsal zaman (non deterministic Polynomial Time) anlamına gelir. P problemlerinin aksine NP problemleri polinomsal zamanda çözülemez çözümleri çok uzun sürebilir lakin var olan bir çözümün doğruluğu ya da yanlışlığı polinomsal bir zamanda kontrol edilebilir. P problemleri NP problemlerinin alt başlığıdır diyebiliriz çünkü bütün P problemleri polinomsal zamanda çözülebilmenin yanı sıra polinamsal zamanda da kontrol edilebilir.
Nedir Bu Problem? Neden Bu Kadar Önemli
P=NP ise kısaca çözümü hızlı bir şekilde doğrulanabilen her problemin aynı zamanda hızlı bir şekilde çözülüp çözülemeyeceğini sorar. Hızlı çözülebilen P problemlerinin hızlı doğrulanabildiğini biliyoruz ancak hızlı doğrulanabilen NP problemlerinin hepsinin hızlı bir şekilde çözülebileceğini söyleyebilir miyiz? Genel olarak sorunun cevabı hayır olsa da henüz ispatlanabilmiş bir problem değildir. Asal sayı bulma probleminin P bir problem olduğunu anlamamız sonucu acaba tüm NP problemler P olabilir mi sorusunun kıymeti artmıştır.
Problemi bu kadar önemli kılan şeyse doğruluğunun ispatı sonucunda ekonomi, biyoloji gibi pek çok alandaki problemler bilgisayarlar tarafından kolaylıkla çözülebilecek olmasıdır. Tabii kriptoloji algoritmaları da bu sınıfa dahildir. Bunların çözümü ise pek de iyi şeylere yol açmayacaktır. Şifreler kolay çözülemeyip kolay kontrol edilebildiği için güvenli ve kullanışlılar. Kolay çözülebildiği takdirde güvenlik diye bir şey kalmayacaktır.
Referanslar
https://www.geeksforgeeks.org/types-of-complexity-classes-p-np-conp-np-hard-and-np-complete/
https://en.wikipedia.org/wiki/Time_complexity#Polynomial_time
Daha fazlası için
https://www.claymath.org/wp-content/uploads/2022/06/pvsnp.pdf
