11
tidak praktis. Dari segi komputasi, permasalahan dalam klasifikasi ini
dapat dibedakan menjadi tiga kategori, yaitu :
1.
Permasalahan Tractable (mudah dari segi komputasi)
Suatu masalah dikatakan tractable, jika masalah tersebut dapat
dipecahkan oleh suatu algoritma yang efisien. Contohnya,
masalah penentuan bilangan terbesar di antara n
bilangan,
penentuan lintasan terpendek antara dua buah vertex di dalam
sebuah graph, dan lain sebagainya.
2.
Permasalahan Intractable (sukar dari segi komputasi)
Suatu masalah dikatakan intractable, jika tidak ada algoritma
yang efisien untuk memecahkan masalah tersebut.
3.
Permasalahan NP-Complete
(NP singkatan dari Non-
Deterministik Polinomial)
Suatu masalah dikatakan NP-Complete
apabila masalah itu
telah berhasil dibuktikan termasuk dalam masalah intractable.
Contohnya, permasalahan pewarnaan graph.
2.
Permasalahan yang tidak
dapat dipecahkan (undecidable / unsolvable
problem)
permasalahan yang termasuk dalam klasifikasi ini adalah semua
permasalahan yang tidak mempunyai aloritma solusi, maksudnya adalah
tidak dapat dilakukan perhitungan, atau tidak dapat diperoleh jawaban
dalam waktu terbatas. Contohnya, permasalahan unbounded tiling.
 |