gg arrow Matematik makaleleri arrow P ile NP arasindaki iliski
P ile NP arasindaki iliski Yazdır E-Posta

P harfi "polynomial", NP harfleri ise "non-deterministic polynomial" ifadelerini temsil eder, türkçe karsiliklari "polinom" ve "belirleyici olmayan polinom"dur. "P esittir NP?" ise Hesaplama Teorisi'nin en temel ve meshur problemidir

P harfi "polynomial", NP harfleri ise "non-deterministic polynomial" ifadelerini temsil eder, türkçe karsiliklari "polinom" ve "belirleyici olmayan polinom"dur. "P esittir NP?" ise Hesaplama Teorisi'nin en temel ve meshur problemidir.

Polinomsal zamanda çözülen problemler

Hesaplama teorisinde, bazi tip problemlerin çözümü için en etkili algoritmalarin çalisma süresinin girilen verinin büyüklügüne bir polinom cinsinden bagli oldugu bilinmektedir (buna polinomsal zamanda çalisan algoritma adi verilir), bu tür problemler P kategorisindeki problemlerdir.

Mesela verilen basamakli bir sayinin asal olup olmadigini kontrol etmek için çalisma süresi mertebesinde bir polinomla hesaplanabilen bir algoritma vardir. Dolayisiyla verilen bir sayinin asal olup olmadiginin arastirilmasi P kategorisinde bir problemdir.

Polinomsal zamanda çözülemeyen problemler

Buna karsilik bir diger gurup problem vardir ki bunlar için sorulan soruya girilen verinin büyüklügüne polinom mertebesinde bagimli bir sürede cevap verecek bir algoritma bilinmemektedir. Fakat bu tür bazi problemler için eger bir sekilde cevabi tahmin edebiliyorsak, tahminimizin dogrulugunu sinamak için veri büyüklügüne polinom mertebesinde bagimli sürelerde çalisacak algoritmalar vardir.

Bu tür problemler, yani bir tahminin dogrulugunun kontrolü için çalisma süresi verinin büyüklügüne polinom cinsinden bagimli bir algoritma olan problemler de NP kategorisini olustururlar. Örnek olarak verilen basamakli bir sayinin asal çarpanlarinin neler oldugu sorusunu düsünebiliriz.

Bu sorunun cevabi için bilinen en iyi algoritmanin çalisma süresi sayisina bir polinom cinsinden degil de eksponansiyel fonksiyonlar cinsinden (misali) bagimlidir (buna üstel zamanda çalisan algoritma denir), fakat bu problem için eger bir sekilde cevabi tahmin edebiliyorsak tahminimizin dogrulugunu sinamak için sayisina polinom mertebesinde bagimli bir sürede çalisacak bir algoritma mevcuttur. Dolayisiyla verilen bir n basamakli sayinin asal çarpanlarinin neler oldugu sorusu NP kategorisindedir.

P ve NP arasindaki bag

Bu iki kategoriden NP'nin P'yi içerdigini görmek kolaydir. Eger bir sorunun cevabini verinin büyüklügüne polinom mertebesinde bagimli sürede çalisacak bir algoritmayla bulabiliyorsak, bu soruya cevap olarak üretilmis bir tahminin dogrulugunu da verinin büyüklügüne polinom mertebesinde bagimli sürede çalisacak bir algoritmayla kontrol edebiliriz.

Bunun için verilen sorunun cevabini verecek algoritmayi çalistirip, onun verdigi cevabi kendi tahminimizle karsilastirmak yeterlidir. "P=NP?" problemi bunun tersinin de dogru olup olmadigini sorar. Yani NP kategorisinde olup da P kategorisinde olmayan problemler var midir? Veya diger bir dille asal çarpanlarin bulunmasi için polinom mertebesinde bir sürede çalisacak bir algoritma gerçekten yok mu yoksa var da biz mi bulamiyoruz?

Bu alanin uzmanlarinin çogunun görüsü bu tür algoritmalarin gerçekten de var olmadiklari için bulunamadigi (yani P nin NP'ye esit olmadigi) seklinde ancak bu soruya kesin bir cevap verilebilmesi simdilik çok zor gözüküyor

<Önceki   Sonraki>
MATEMATİKÇİ PULU
HİPERBOLİK UZAY
FOTO MATEMATİK
C.Sequin Galeri
MATEMATİK AFİŞİ
G.W.Hart galeri
KARİKATÜR
M.C.Escher galeri
MATEMATİK KİTABI
MATEMATİK FİLMİ