np-complete çevirisi yanıltıcı

[alper111]

np-complete ingilizce tanımı: problems that are solved in polynomial time by a non-deterministic turing machine. Türkçe çevirisinde ise "çokterimli zamanda bulunamaz" şeklinde geçiyor. Fakat bu yanlış bir kullanım. NP sınıfı çoğu zaman "non-polynomial time" şeklinde karıştırılıyor. Fakat asıl açılımı "non-deterministic polynomial time". Biz henüz bu sınıftaki problemlerin çokterimli zamanda bulunamayacağını kanıtlayamadık.

NP-complete sınıfını NP sınıfından ayıran fark ise NP sınıfındaki her problemi çokterimli zaman kullanarak NP-complete sınıfındaki bir probleme eşleyebilmemiz. Bu nedenle NP-complete sınıfındaki herhangi bir probleme çokterimli zamanda bir çözüm üretirsek, P=NP doğru oluyor.

Bu sınıfların harf kısaltmaları aynı şekilde kullanılabilir. Doğal sayı kümesine N dediğimiz gibi.