P ile NP arasındaki ilişki sayfasının kaynağını görüntüle

{{Kaynaksız|tarih=Temmuz 2024}}
[[Dosya:Complexity classes.png|küçükresim|P ve NP karmaşıklık sınıfları için bir diyagram.]]
[[P (karmaşıklık)|P]] harfi "polynomial", [[NP (karmaşıklık)|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.

== 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 <math>n \,</math> basamaklı bir sayının [[Asal Sayılar|asal]] olup olmadığını kontrol etmek için çalışma süresi <math>n^6 \,</math> 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 <math>n \,</math> 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 <math>n \,</math> sayısına bir polinom cinsinden değil de eksponansiyel fonksiyonlar cinsinden (<math>e^n \,</math> 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 <math>n \,</math> sayısına polinom mertebesinde bağımlı bir sürede çalışacak bir algoritma mevcuttur. Dolayısıyla verilen bir <math>n</math> 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.

== Ayrıca bakınız == 
*[[NP (karmaşıklık)]]

[[Kategori:Karmaşıklık teorisi]]
[[Kategori:Optimizasyon]]
[[Kategori:Konjektürler]]
[[Kategori:Çözülememiş matematik problemleri]]
[[Kategori:Çözülememiş bilgisayar bilimi problemleri]]
[[Kategori:Millennium Prize Problemleri]]