DAA - P & NP Sınıfı
Bilgisayar Biliminde, amacın bazı değerleri maksimize etmek veya en aza indirmek olduğu birçok sorun çözülür, oysa diğer problemlerde bir çözüm olup olmadığını bulmaya çalışırız. Dolayısıyla sorunlar aşağıdaki şekilde kategorize edilebilir:
Optimizasyon Sorunu
Optimizasyon sorunları, amacı bazı değerleri maksimize etmek veya en aza indirmek olan problemlerdir. Örneğin,
Belirli bir grafiği renklendirmek için gereken minimum renk sayısını bulmak.
Bir grafikteki iki köşe arasındaki en kısa yolu bulmak.
Karar Problemi
Cevabın Evet veya Hayır olduğu birçok sorun vardır. Bu tür sorunlar olarak bilinir. decision problems. Örneğin,
Belirli bir grafiğin yalnızca 4 renkle renklendirilip renklendirilemeyeceği.
Hamilton döngüsünü bir grafikte bulmak bir karar problemi değildir, oysa bir grafiğin kontrol edilmesi bir karar problemidir.
Dil nedir?
Her karar sorunun sadece iki cevabı olabilir, evet veya hayır. Dolayısıyla, belirli bir girdi için 'evet' yanıtı veriyorsa, bir karar problemi bir dile ait olabilir. Bir dil, cevabı Evet olan girdilerin toplamıdır. Önceki bölümlerde tartışılan algoritmaların çoğupolynomial time algorithms.
Giriş boyutu için n, bir algoritmanın en kötü durum zaman karmaşıklığı ise O(nk), nerede k bir sabittir, algoritma bir polinom zaman algoritmasıdır.
Matris Zinciri Çarpımı, Tek Kaynaklı En Kısa Yol, Tüm Çiftler En Kısa Yol, Minimum Yayılma Ağacı, vb. Gibi algoritmalar polinom zamanda çalışır. Bununla birlikte, seyyar satış elemanı, optimal grafik renklendirme, Hamilton döngüleri, bir grafikte en uzun yolu bulma ve hiçbir polinom zaman algoritmasının bilinmediği bir Boole formülünü karşılama gibi birçok sorun vardır. Bu sorunlar ilginç bir sorun sınıfına aittir.NP-Complete durumu bilinmeyen sorunlar.
Bu bağlamda sorunları şu şekilde sınıflandırabiliriz -
P-Sınıfı
P sınıfı, polinom zamanda çözülebilen problemlerden oluşur, yani bu problemler zaman içinde çözülebilir. O(nk) en kötü durumda, nerede k sabittir.
Bu sorunlara tractablediğerleri çağrılırken intractable or superpolynomial.
Resmi olarak, bir algoritma polinom zaman algoritmasıdır, eğer bir polinom varsa p(n) öyle ki algoritma herhangi bir boyut örneğini çözebilir n bir süre içinde O(p(n)).
Gerektiren sorun Ω(n50) çözme süresi esasen büyük n. En çok bilinen polinom zaman algoritması zamanda çalışırO(nk) oldukça düşük değer için k.
Polinom zamanlı algoritmalar sınıfını dikkate almanın avantajları, tümünün makul olmasıdır. deterministic single processor model of computation en fazla bir polinom yavaş-d ile birbirleri üzerinde simüle edilebilir
NP Sınıfı
NP sınıfı, polinom zamanında doğrulanabilen problemlerden oluşur. NP, iddia edilen bir cevabın doğruluğunu biraz fazladan bilgi yardımıyla kontrol etmenin kolay olduğu karar problemleri sınıfıdır. Bu nedenle, bir çözüm bulmanın bir yolunu değil, yalnızca iddia edilen bir çözümün gerçekten doğru olduğunu doğrulamak için soruyoruz.
Bu sınıftaki her problem, kapsamlı arama kullanılarak üstel zamanda çözülebilir.
P ve NP
Bir deterministik polinom zaman algoritması ile çözülebilen her karar problemi, aynı zamanda, bir polinom zamanlı deterministik olmayan algoritma ile de çözülebilir.
P'deki tüm problemler polinom zaman algoritmaları ile çözülebilirken, NP - P'deki tüm problemler çözülemez.
Bilinmemektedir P = NP. Bununla birlikte, NP'de, eğer P'ye aitlerse, P = NP olduğu kanıtlanabileceği özelliğiyle bilinen birçok problem vardır.
Eğer P ≠ NPNP'de ne P'de ne de NP-Complete'de olmayan sorunlar var.
Sorun sınıfa ait Psorun için bir çözüm bulmak kolaysa. Sorun şuna aitNP, bulmak çok sıkıcı olabilecek bir çözümü kontrol etmek kolaysa.