P, NP, NPC Problemler ne demektir?

Hesaplama teorisi (Theory of computation) bilgisayar biliminin bir problemin belirli bir algoritma ve hesap modeli ile çözülüp çözülemeyeceğini veya çözülürse ne kadar hızlı ve verimli bir şekilde çözüleceğini inceleyen bilim dalıdır.
Başlıca 2 dala ayrılır:
Karmaşıklık Teorisi (Complexity Theory) ve
Hesaplanabilirlik Teorisi (Computability Theory).

Karmaşıklık teorisi genelde karar verme problemleri (decision problems) ile uğraşır. Karar verme problemi sorulan bir soruya evet ya da hayır olarak cevap verebilme ile ilgilidir. Mesela, verilen herhangi bir sayı için “asal mı” (IS-PRIME) sorusuna evet ya da hayır olarak cevap verebilme problemi bir karar verme problemidir. Bu tip problemler özellikle incelenmektedir çünkü herhangi bir problem bir karar verme problemine indirgenebilir ve bu sayede çözüme ulaştırılabilir. Örneğin; “çarpanı var mı” (HAS-FACTOR) problemi bir sayının yine verilen bir sayıdan küçük asal çarpanı olup olmadığı sorusuna cevap verir. Bu problemi çözebilirsek verilen herhangi bir sayının asal çarpanlarını bulma sorununa da aynı zamanda çözmüş oluruz.

Hesaplama karmaşıklığı teorisi (computational complexity theory) bilgisayar biliminde hesaplama teorisinin bir alt dalı olarak sınıflandırılır. Bir algoritmanın bir problem üzerinde çalıştırılması durumunda ne kadar kaynağa gereksinim olduğunu inceleyen bilim dalıdır. Bu teori, bir girdinin büyüklüğü artırıldığında buna bağlı olarak algoritmanın çalışma zamanının ve hafıza ihtiyaçlarının ne kadar arttığını araştırır. Algoritmaların karmaşıklığı genelde zamanla bağlantılı olarak ölçülür ve büyük O (big O notation) ile ifade edilir. Örneğin O(n), O(n2) sırasıyla n büyüklüğündeki bir veri girildiğinde bu algoritmanın yavaşlığının o girdinin büyüklüğüyle doğru orantılı olarak arttığını gösterirken, n2 olan ise bu girdinin büyüklüğünün karesiyle doğru orantılı olarak değiştiğini gösterir.

Karmaşıklık teorisinde problemler çözülebildikleri en hızlı karmaşıklığa göre karmaşıklık sınıflarına (computational complexity) ayrılırlar. Bunlardan en önemlileri
P (deterministically polynomial, deterministik polinomsal) ve
NP(non- deterministically polynomial- deterministik olmayan polinomsal)’dir.

P kategorisine giren problemler karmaşıklığı O(nk), k ∈ R ile ifade edilebilen ve deterministik Turing makinesinde polinomsal zamanda çözülebilen problemlerdir. Örneğin; en büyük ortak bölen bulma ya da sıralı bir liste içinde arama yapma polinomsal zamanda çözülebilir ve bu yüzden P sınıfı problemlerdir.

NP problemler ise en büyük karmaşıklık sınıflarından birini oluşturur. Hatta P sınıfı da NP sınıfının içinde gösterilir. NP problemler deterministik olmayan Turing makinesiyle polinomsal zamanda çözülebilirler. Günümüzde deterministik olmayan bir Turing makinesi bulunmadığından NP problemler için verimli kabul edilebilecek bir algoritma bulunamamıştır. Örneğin; 2 çizgenin (graph) izomorfik olup olmadığının hesaplanması yani 2 çizgenin aynı şekli oluşturacak şekilde çizilip çizilemeyeceğinin hesaplanması polinomsal zamanda yapılamamaktadır.

NP sınıfına dâhil olan problemlerin bazıları o kadar zordur ki bunlara polinomsal zaman bulmak teşebbüsleri çok uzun uğraşlardan sonra sonuçsuz kalmıştır. Bu sınıfa NP-Complete adı verilir. Bir problemin NP-Complete (NPC) sınıfında olduğu kabul edilmişse o problem için polinomsal zaman bulunmasının çok zor olduğu anlaşılabilir.

Yıllardan beri NP sınıfı içindeki problemler çözülmeye çalışılmıştır ancak çok azı dışında bu başarılamamıştır. İlerlemeler ise umut vericidir. NPC problemlerin herhangi biri polinomsal zamanda çözülebilirse, NP sınıfındaki tüm problemlerin de polinomsal zamanda çözülebileceğini ispatlayan bir makale yayınlanmış ve tabi ki bununla da bilgisayar biliminde çok büyük bir devrim gerçekleşmiştir. 1971 yılında bir bilgisayar bilimci olan Stephen Cook “The complexity of theorem proving procedures” adlı bilimsel yazısında bugün Cook teoremi olarak bilinen bir teoremi ispatlamıştır. Bu teoremde “Mantıksal Sağlanabilirlik” probleminin (Boolean satisfiability Problem) NP-Complete olduğunu göstermiştir. Biraz daha açıklamak gerekirse NP sınıfındaki herhangi bir problem polinomsal zamanda deterministik Turing makinesi tarafından bir mantıksal formülünün sağlanabilir olup olmadığı problemine indirgenebilir. Bu teoremin bize sağladığı en büyük yarar ise; eğer mantıksal sağlanabilirlik problemine deterministik ve polinomik bir çözüm bulunursa, NP deki tüm problemlerin de aynı şekilde çözülebileceğini ispatlamış olmasıdır. Aynı şey elbette PC olan tüm problemler için de geçerlidir. Bu sorun “P=NP?” sorunu olarak bilinir ve literatürdeki en ünlü ve en önemli problemdir. Hatta Clay Matematik Enstitüsü herhangi bir NPC problemini çözene 1 milyon $ vaat etmektedir.

Kaynak: http://e-bergi.com/y/Hesaplama-Karmasikligi