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.
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 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 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 sayısına bir polinom cinsinden değil de eksponansiyel fonksiyonlar cinsinden ( misali) bağımlıdır (buna denir), fakat bu problem için eğer bir şekilde cevabı tahmin edebiliyorsak tahminimizin doğruluğunu sınamak için sayı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.
Ayrıca bakınız
wikipedia, wiki, viki, vikipedia, oku, kitap, kütüphane, kütübhane, ara, ara bul, bul, herşey, ne arasanız burada,hikayeler, makale, kitaplar, öğren, wiki, bilgi, tarih, yukle, izle, telefon için, turk, türk, türkçe, turkce, nasıl yapılır, ne demek, nasıl, yapmak, yapılır, indir, ücretsiz, ücretsiz indir, bedava, bedava indir, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, resim, müzik, şarkı, film, film, oyun, oyunlar, mobil, cep telefonu, telefon, android, ios, apple, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, pc, web, computer, bilgisayar
P harfi polynomial NP harfleri ise non deterministic polynomial ifadelerini temsil eder Turkce karsiliklari polinom ve belirleyici olmayan polinom dur P esittir NP ise hesaplama teorisi nin en temel ve meshur problemidir Polinomsal zamanda cozulen problemlerHesaplama teorisinde bazi tip problemlerin cozumu icin en etkili algoritmalarin calisma suresinin girilen verinin buyuklugune bir polinom cinsinden bagli oldugu bilinmektedir buna polinomsal zamanda calisan algoritma adi verilir bu tur problemler P kategorisindeki problemlerdir Mesela verilen n displaystyle n basamakli bir sayinin asal olup olmadigini kontrol etmek icin calisma suresi n6 displaystyle n 6 mertebesinde bir polinomla hesaplanabilen bir algoritma vardir Dolayisiyla verilen bir sayinin asal olup olmadiginin arastirilmasi P kategorisinde bir problemdir Polinomsal zamanda cozulemeyen problemlerBuna karsilik bir diger grup problem vardir ki bunlar icin sorulan soruya girilen verinin buyuklugune polinom mertebesinde bagimli bir surede cevap verecek bir algoritma bilinmemektedir Fakat bu tur bazi problemler icin eger bir sekilde cevabi tahmin edebiliyorsak tahminimizin dogrulugunu sinamak icin veri buyuklugune polinom mertebesinde bagimli surelerde calisacak algoritmalar vardir Bu tur problemler yani bir tahminin dogrulugunun kontrolu icin calisma suresi verinin buyuklugune polinom cinsinden bagimli bir algoritma olan problemler de NP kategorisini olustururlar Ornek olarak verilen n displaystyle n basamakli bir sayinin asal carpanlarinin neler oldugu sorusunu dusunebiliriz Bu sorunun cevabi icin bilinen en iyi algoritmanin calisma suresi n displaystyle n sayisina bir polinom cinsinden degil de eksponansiyel fonksiyonlar cinsinden en displaystyle e n misali bagimlidir buna denir fakat bu problem icin eger bir sekilde cevabi tahmin edebiliyorsak tahminimizin dogrulugunu sinamak icin n displaystyle n sayisina polinom mertebesinde bagimli bir surede calisacak bir algoritma mevcuttur Dolayisiyla verilen bir n displaystyle n basamakli sayinin asal carpanlarinin neler oldugu sorusu NP kategorisindedir P ve NP arasindaki bagBu iki kategoriden NP nin P yi icerdigini gormek kolaydir Eger bir sorunun cevabini verinin buyuklugune polinom mertebesinde bagimli surede calisacak bir algoritmayla bulabiliyorsak bu soruya cevap olarak uretilmis bir tahminin dogrulugunu da verinin buyuklugune polinom mertebesinde bagimli surede calisacak bir algoritmayla kontrol edebiliriz Bunun icin verilen sorunun cevabini verecek algoritmayi calistirip 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 carpanlarin bulunmasi icin polinom mertebesinde bir surede calisacak bir algoritma gercekten yok mu yoksa var da biz mi bulamiyoruz Bu alanin uzmanlarinin cogunun gorusu bu tur algoritmalarin gercekten de var olmadiklari icin bulunamadigi yani P nin NP ye esit olmadigi seklinde ancak bu soruya kesin bir cevap verilebilmesi simdilik cok zor gozukuyor Ayrica bakinizNP karmasiklik