P İle Np Arasındaki İlişki Nedir?

**Prof. Dr. Sinsi** · 12-19-2012

[size="3">P harfi "]Polinomsal zamanda çözülen problemler[/size][/b]

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

basamaklı bir sayının asal olup olmadığını kontrol etmek için çalışma süresi 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

asamaklı 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

sayısına bir polinom cinsinden değil de eksponansiyel fonksiyonlar cinsinden (

ayısına polinom mertebesinde bağımlı bir sürede çalışacak bir algoritma mevcuttur

Dolayısıyla verilen bir

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

12-19-2012	#1
Prof. Dr. Sinsi	P İle Np Arasındaki İlişki Nedir? [size="3">P harfi "]Polinomsal zamanda çözülen problemler[/size][/b] 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 basamaklı bir sayının asal olup olmadığını kontrol etmek için çalışma süresi 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 asamaklı 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 sayısına bir polinom cinsinden değil de eksponansiyel fonksiyonlar cinsinden ( ayısına polinom mertebesinde bağımlı bir sürede çalışacak bir algoritma mevcuttur Dolayısıyla verilen bir 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