NP-complete Problems

Ini konsep yang cukup rumit, tapi tampaknya ini semacam klasifikasi untuk Computational Problem yang sulit untuk ditemukan algoritma efisiennya.

Buku Introduction to Algorithms membawakan 3 alasan kenapa masalah NP-complete sangat menarik:

1. Meskipun belum ditemukan algoritma efisien untuk masalah-masalah NP-complete, tidak ada yang pernah dapat membuktikan bahwa algoritma efisiennya mustahil untuk ditemukan juga
2. Seperangkat masalah NP-complete punya properti terkenal yang membuat jika algoritma efisien dapat ditemukan untuk salah satu dari mereka, maka berarti algoritma efisien ada untuk mereka semua
3. Beberapa masalah NP-complete itu mirip, walau tidak identik, dengan masalah yang dapat kita ketahui algoritma efisiennya.

Salah satu yang terkenal adalah Traveling Sales-person Problem.