Yazan : Şadi Evren ŞEKER
Bilgisayar bilimlerinde problem sınıflamada kullanılan sınıflardan birisidir. Bu sınıfa giren problemler için çözümleme zamanı arttıkça artan (super increasing) yapıya sahip olmaktadır. Buna göre her adımdaki çözümleme zamanı kendinden çözümleme zamanlarından daha fazladır.
Problem yapı olarak artan zamanda çözüldüğü için de bu problem tiplerinin çokterimli zamanda (polynomial time) çözülmesi mümkün değildir. Bu problemin tanımında ayrıca Turing Makinesinden de yararlanılır.
Turing makineleri beliri (deterministic) ve belirsiz (nondeterministic) olarak ikiye ayrılır. Buna göre NP-Complete bir problem Belirsiz Turing Makinesi tarafından belirli zamanda çözülebilmektedir.
Ayrıca problemleri kümelerken diğer bir küme olan P kümesi yani çokterimli (polynomial) kümesi, NP kümesinin bir alt kümesi olarak kabul edilir.
Bir problemin NP kümesinde olduğunu ispatlamanın yollarından birisi de bu problemi NP kümesinde bulunan başka bir probleme dönüştürmektir.
En meşhur problemlerden bazıları:
Altküme toplam problemi
RSA
Merkle-Hellman
Hocam çok teşekkür ederim.