Combinatorial Problem

Dari perspektif yang lebih abstrak, masalah salesman bepergian dan masalah mewarnai grafik, adalah contoh dari masalah kombinatorial. Ini adalah masalah yang meminta, secara eksplisit atau implisit, untuk menemukan benda seperti kombinatorial sebagai permutasi, kombinasi, atau bagian yang memenuhi kendala tertentu. Diinginkanya sebuah objek kombinatorial juga mungkin diperlukan untuk memiliki beberapa properti tambahan seperti sebagai nilai maksimum atau biaya minimum.
Secara umum, masalah kombinatorial adalah masalah yang paling sulit di komputasi, baik dari sudut pandang teoritis dan praktis. kesulitan mereka berasal dari fakta-fakta berikut. 
Pertama, jumlah objek kombinatorial biasanya tumbuh sangat cepat dengan masalah pada ukuran, mencapai besaran yang tak terbayangkan bahkan untuk contoh berukuran sedang. 
Kedua, tidak ada algoritma untuk memecahkan kebanyakan masalah seperti persis dalam jumlah yang diterima waktu. Selain itu, sebagian besar ilmuwan komputer percaya bahwa algoritma tersebut tidak ada. Dugaan ini telah terbukti atau tidak terbukti, dan tetap menjadi masalah penting yang belum terpecahkan dalam ilmu komputer teoritis. 

Sumber :
- Levitin, Anany. Introduction to The Design and Analysis of Algorithms