NP-Hard problem ne demektir?

Öncelikle, aktaracağım sınırlı bilgilerde hata payımın olduğunu belirtmek isterim. Zira, ben de sınırlı kaynaktan zorlanarak konu hakkında bilgi edindim. Ama yine de paylaşmak istiyorum. Belki birbirimize yardımcı oluruz.

İlk olarak, P ve NP kompleks hesaplama teoreminden gelen sınıfları ifade eden ön eklerdir. Hesaplama teoremine göre P sınıfında yer alan problemler Polynomial zamanda çözülebilecek problemleri ifade etmek için kullanılmaktadır. Yani problemin zorluğu arttığında çözüm süresi polinomsal olarak (n^2, n^3 gibi) artar. Öte yandan, NP sınıfındaki problemlerin çözümü ise NonDeterministic-Polynomial zamanda çözümlenebilir. Problem karmaşıklaştıkça çözüm süresi üssel biçimde (2^n, 3^n gibi) artmaktadır.

Hal böyleyken P ve NP sınıfındaki problemler az çok belirlenmiştir. Matematiksel formüllerine bakılarak, benzetilerek bir problemin ne kadar 'zor' olduğuna ya da çözümünün ne kadar mümkün olduğuna karar verilmektedir. Buna ek olarak, NP sınıfındaki problemler de kendi içinde sınıflandırılmıştır biraz literatür taraması yaparak probleminizin ait olduğu sınıfı öğrenmeniz mümkün olacaktır.

NP sınıfında da problemler NP-Hard ve NP-Complete olarak ikiye ayrılmaktadır. NP-Complete problemler karmaşıklık sınıfına ait en zor problemlerin bulunduğu sınıftır ve probleminiz bu sınıftaysa doğrudan bir çözüm bulmanız oldulça zordur. Öte yandan, NP-Hard sınıfındaki problemler ise NP sınıfındaki problemler kadar zor olmasına rağmen P sınıfındaki problemlere indirgenebilenleri ifade etmektedir. Yani NP sınıfının görece 'kolay' problemlerini içerir. Bu NP'den P'ye indirgemek nasıl olur diye aklınıza gelirse diye ilginç bir bilgi daha paylaşayım bu P versus NP problemi, çözülmeyi bekleyen milyon dolar ödüllü bir problemmiş.

Derinlemesine bilgi sahibi olmadığımı en başından belirttiğim bu konuda, umarım yardımcı olabilmişimdir.

Kısa bir ekleme yapmak gerekirse, eğer algoritmanız net bir şekilde yapılacak işi tanımlamış ise, ihtiyacınız olan işlemci gücü ve kapasitesine göre probleminizin çözülmesine ilişkin öngörüm yapabilirsiniz.

Biraz benzetimle P tipi problemler havuz problemleri gibidir, işci havuz musluk yani problem, cpu ve ram biliniyorsa doldurma işi için doldurma veya boşaltma zamanı net bir şekilde hesaplanabilir,

NP tipi problemler Deterministik olmayan yani net bir formülle bağımlı ve bağımsız değişkenleri şekillendiremediğiniz problemlerdir ve havuz problemnine yağmur, komşunun cocuklarının havuza hortum atması, havuzdan su içen kuşlar, kaza yapan bir tankerin havuzunuza düşme ihtimali vb gibi formüle katmakta dolayısı ile hesaplama zamanını polinomsal bir formüle dökmekte sorun yaşayacağınız tipte problemlerdir.

"NP zor sorunlar olarak en azından sert", gayrı olan sorunların bir sınıftır.
Bir sorun
H

NP-zor
olmadığını ve yalnızca

bir olduğunu
NP-tam

olduğunu sorun L
polinom zaman Turing indirgenebilir

(örneğin, L ≤ H 

T

H) .
Diğer bir deyişle,
L

çözülebilir
polinom zamanda

bir tarafından
kehanet makine

için bir kahinin ile
H

.
Gayriresmi olarak, biz çözmek için bir alt yordam gibi bir kahin makinesi diyebileceğimiz bir algoritma düşünebilirsiniz
H

, ve çözer
L

altprogram çağrısı hesaplamak için sadece bir adım alırsa, polinom zamanda.