:::: MENU ::::

NP, NP-Complete, NP-Hard nedir?

NP, NP-Complete, NP-Hard nedir?

Bir problem Evet veya Hayır şeklinde sonuç üretiyorsa buna karar problemi denir.

P (Polynomial Time): Polinomsal zamanda çözülebilen karar problemlerinin karmaşıklık sınıfıdır. Yani polinomsal zamanda Evet veya Hayır şeklinde bir çözüm üretilir.

NP (Non-deterministic-polynomial Time): Polinomsal zamanda doğrulanabilen karar problemlerinin karmaşıklık sınıfıdır. Burada problemin bir çözümü olup olmadığı ile ilgilenilmiyor.

NP-Complete: Her adımdaki çözümleme zamanı kendinden önceki adımdaki çözümleme zamanlarından daha fazla olduğu için bu problem tiplerinin çokterimli zamanda (polynomial time) çözülmesi mümkün değildir. NP-Complete bir problem Belirsiz(Non-Deterministic) Turing Makinesi tarafından belirli zamanda çözülebilmektedir.

NP-Hard: Polinomsal zamanda bir çözümü olduğunu ispatlayamadığımız karar problemlerinin karmaşıklık sınıfıdır.3SAT ve Halting problemi NP-Hard problemlerdir.

P=NP? sorusunun cevabı aranmaktadır. P=NP ispatlanabilirse çözümü olmayan problemlere de çözümler üretilecektir.

Aşağıdaki her iki durum için karmaşıklık sınıfları görselleştirilmiştir:

P-NP-NP-Complete-NP-Hard


Görüşlerinizi önemsiyorum...