NP (karmaşıklık)
Günümüz dünyasında, NP (karmaşıklık) geniş bir insan kitlesi için büyük önem taşıyan ve ilgi duyulan bir konu haline geldi. Alanında uzmanlardan konuyla ilgili bilgi arayanlara kadar NP (karmaşıklık) dünya çapında pek çok kişinin dikkatini çekti. Pek çok yönü ve günlük yaşamın farklı yönleri üzerindeki etkisiyle NP (karmaşıklık), tartışma ve düşünmenin odak noktası haline geldi. Bu makalede, NP (karmaşıklık)'i ve sonuçlarını yakından inceleyerek bu büyüleyici konu hakkında ayrıntılı analizler ve farklı bakış açıları sunacağız.
Nen karar problemlerini içeren karmaşıklık sınıfıdır.
Bu sınıftaki problemler belirli Turing Makinesi ile çokterimli zamanda doğrulanabilirler ve bu şekilde doğrulanabilen her problem NP sınıfındadır. Bu nedenle NP, (belirli Turing Makinesi ile) çokterimli zamanda doğrulanabilen problemlerin sınıfı olarak da tanımlanabilir.
Belirli Turing makinesi aynı zamanda belirsiz Turing makinesi olduğundan, P sınıfındaki bütün problemler aynı zamanda NP'dedir.
NP-Zor
En az her bir NP problem kadar zor olan problemlerin bulunduğu sınıfa NP-Zor (NP-hard) denir. Daha resmi bir şekilde,
Burada , L probleminin, H problemine çokterimli zamanda indirgenebildiği anlamına gelir.
Bir başka deyişle, NP-Zor sınıfındaki herhangi bir problem çok terimli zamanda çözülebilirse, NP sınıfındaki bütün problemler çok terimli zamanda çözülebilir.
NP-Tam
NP-Tam (NP-complete), hem NP olup hem NP-Zor olan problemlerin sınıfıdır. Dolayısıyla bu sınıftaki problemler NP sınıfının en zor problemleridir. Yukarıdaki tanımdan yola çıkarak, herhangi biri çokterimli zamanda çözülebilirse, bütün hepsi çok terimli zamanda çözülebilir.
NP-Tam örnekleri
- İkilik tatmin edilebilirlik (CNF-SAT)
- Dolaşan satıcı (TSP)
- Hamilton dönüşü ve Hamilton yolu
- Hamilton yolu problemi
- Cook-Levin teoremi
- Alt küme toplamı problemi
- Bağımsız küme problemi
- Düğüm kapsama problemi
Bunlardan CNF-SAT ya da kısaca SAT, tarihsel olarak NP-Tam olduğu ispatlanan ilk problemdir.