P ile NP arasındaki ilişki

bullvar_katip · 21 Mayıs 2024

P harfi "polynomial", NP harfleri ise "non-deterministic polynomial" ifadelerini temsil eder, Türkçe karşılıkları "polinom" ve "belirleyici olmayan polinom"dur. "P eşittir NP?" ise hesaplama teorisi'nin en temel ve meşhur problemidir. Polinomsal zamanda çözülen problemler Hesaplama teorisinde, bazı tip problemlerin çözümü için en etkili algoritmaların çalışma süresinin girilen verinin büyüklüğüne bir polinom cinsinden bağlı olduğu bilinmektedir (buna polinomsal zamanda çalışan algoritma adı verilir), bu tür problemler P kategorisindeki problemlerdir. Mesela verilen basamaklı bir sayının asal olup olmadığını kontrol etmek için çalışma süresi mertebesinde bir polinomla hesaplanabilen bir algoritma vardır. Dolayısıyla verilen bir sayının asal olup olmadığının araştırılması P kategorisinde bir problemdir. Polinomsal zamanda çözülemeyen problemler Buna karşılık bir diğer grup problem vardır ki bunlar için sorulan soruya girilen verinin büyüklüğüne polinom mertebesinde bağımlı bir sürede cevap verecek bir algoritma bilinmemektedir. Fakat bu tür bazı problemler için eğer bir şekilde cevabı tahmin edebiliyorsak, tahminimizin doğruluğunu sınamak için veri büyüklüğüne polinom mertebesinde bağımlı sürelerde çalışacak algoritmalar vardır. Bu tür problemler, yani bir tahminin doğruluğunun kontrolü için çalışma süresi verinin büyüklüğüne polinom cinsinden bağımlı bir algoritma olan problemler de NP kategorisini oluştururlar. Örnek olarak verilen basamaklı bir sayının asal çarpanlarının neler olduğu sorusunu düşünebiliriz. Bu sorunun cevabı için bilinen en iyi algoritmanın çalışma süresi sayısına bir polinom cinsinden değil de eksponansiyel fonksiyonlar cinsinden ( misali) bağımlıdır (buna üstel zamanda çalışan algoritma denir), fakat bu problem için eğer bir şekilde cevabı tahmin edebiliyorsak tahminimizin doğruluğunu sınamak için sayısına polinom mertebesinde bağımlı bir sürede çalışacak bir algoritma mevcuttur. Dolayısıyla verilen bir basamaklı sayının asal çarpanlarının neler olduğu sorusu NP kategorisindedir. P ve NP arasındaki bağ Bu iki kategoriden NP'nin P'yi içerdiğini görmek kolaydır. Eğer bir sorunun cevabını verinin büyüklüğüne polinom mertebesinde bağımlı sürede çalışacak bir algoritmayla bulabiliyorsak, bu soruya cevap olarak üretilmiş bir tahminin doğruluğunu da verinin büyüklüğüne polinom mertebesinde bağımlı sürede çalışacak bir algoritmayla kontrol edebiliriz. Bunun için verilen sorunun cevabını verecek algoritmayı çalıştırıp, onun verdiği cevabı kendi tahminimizle karşılaştırmak yeterlidir. "P=NP?" problemi bunun tersinin de doğru olup olmadığını sorar. Yani NP kategorisinde olup da P kategorisinde olmayan problemler var mıdır? Veya diğer bir dille asal çarpanların bulunması için polinom mertebesinde bir sürede çalışacak bir algoritma gerçekten yok mu yoksa var da biz mi bulamıyoruz? Bu alanın uzmanlarının çoğunun görüşü bu tür algoritmaların gerçekten de var olmadıkları için bulunamadığı (yani P nin NP'ye eşit olmadığı) şeklinde ancak bu soruya kesin bir cevap verilebilmesi şimdilik çok zor gözüküyor. Ayrıca bakınız NP (karmaşıklık) Kategori:Karmaşıklık teorisi Kategori:Optimizasyon Kategori:Konjektürler Kategori:Çözülememiş matematik problemleri Kategori:Çözülememiş bilgisayar bilimi problemleri Kategori:Millennium Prize Problemleri

Ara

Ara

Foruma hoş geldin 👋, Ziyaretçi

P ile NP arasındaki ilişki

bullvar_katip

Administrator

Benzer konular

Tema özelleştirme sistemi

Tam ekran yada dar ekran

Izgara yada normal mod

Forum arkaplan resimleri

Sidebar blogunu kapat/aç

Yapışkan sidebar kapat/aç

Radius aç/kapat

Foruma hoş geldin 👋, Ziyaretçi