NP Karmaşıklığını Anlamak: Tanım ve Örnekler

NP, "Belirleyici Olmayan Polinom Zamanı" anlamına gelir. Bir problemi çözmek için gereken süreyi ifade eden bir karmaşıklık sınıfıdır. NP'de, bir algoritmanın çalışma süresi, girdi boyutunda polinom olabilir ancak aynı zamanda deterministik de olmayabilir; bu, çalışma süresinin algoritma tarafından seçilen spesifik çözüme bağlı olarak değişebileceği anlamına gelir.

Başka bir deyişle, NP bir Deterministik olmayan bir makinede polinom zamanda çözülebilen problemler sınıfı. Deterministik olmayan bir makine, bir problemin olası tüm çözümlerini paralel olarak deneyebilen ve işe yarayan ilk çözümü kabul edebilen bir makinedir. Bu, makinenin bazı sorunları aynı anda yalnızca tek bir çözümü deneyebilen deterministik bir makineden çok daha hızlı çözmesine olanak tanır. Her şehri tam olarak bir kez ziyaret eden mümkün olan en kısa rotayı bulun)
* Sırt çantası problemi (bir dizi öğe ve bunların ağırlıkları ve değerleri verildiğinde, toplam değeri maksimuma çıkaran sınırlı kapasiteli bir sırt çantasına dahil edilecek öğelerin alt kümesini belirleyin)
* Boole tatmin edilebilirliği problemi (bir dizi boole değişkeni ve bunların kısıtlamaları verildiğinde, değişkenlere tüm kısıtlamaları karşılayan bir değer atamasının olup olmadığını belirleyin)

NP karmaşıklık sınıfı önemlidir çünkü polinomda çözülmesi zor olan birçok problemi içerir. ancak deterministik bir makine tarafından hızlı bir şekilde doğrulanabilir. Bu, bir algoritmanın polinom zamanında bir çözüm bulamamasına rağmen önerilen çözümü hızlı bir şekilde doğrulayabilmesi durumunda yine de yararlı olabileceği anlamına gelir.