- Mesin Turing: Abstraksi komputer yang diciptakan oleh Alan Turing. Ciri utama dari mesin ini adalah pengaksesan memori bersifat sekuensial. Menuju lokasi memori yang lokasinya jauh dari lokasi yang sekarang sedang diakses membutuhkan waktu linear terhadap perbedaan jarak kedua lokasi memori. Kecuali komputer Quantum, semua komputer riil maupun abstrak mempunyai kemampuan tidak lebih besar (dalam batas polinomial terhadap besar input) dari pada mesin Turing.
- Mesin Turing Non-Deterministik (NDTM): Mesin Turing dimana pada setiap saat dimungkinkan ada beberapa alternatif instruksi untuk dieksekusi. Eksekusi keseluruhan otomatis berhenti apabila ada satu dari semua alternatif tersebut yang mencapai instruksi terakhirnya. Konsep ini mirip seperti komputasi paralel, tetapi dengan jumlah prosesor yang tidak dibatasi.
- Mesin Turing Deterministik (DTM): Mesin Turing dimana pada setiap saat hanya ada satu alternatif instruksi untuk dieksekusi. Karena satu alternatif adalah subset dari beberapa alternatif, maka semua komputasi yang dilakukan di DTM dapat juga dilakukan di NDTM.
- Mesin RAM: Abstraksi dari banyak komputer modern yang kita kenal sekarang. Mesin RAM terdiri dari komponen input, output, memori, dan prosesor. Perbedaan utama dari Mesin Turing adalah akses kesetiap lokasi memori membutuhkan waktu konstan. Kemampuan mesin RAM tidak lebih besar dari mesin Turing Deterministik, hanya p(n), polinomial terhadap besar input, lebih cepat dari DTM.
- Kelompok problem NP: Problem komputasi yang mempunyai algoritma pada NDTM dengan kompleksitas waktu p(n), yaitu polinomial terhadap besar input. Implikasinya ada problem komputasi yang bukan NP. Istilah NP terkait dengan nondeterministik polinomial, bukan non-polinomial.
- Kelompok problem P: Problem komputasi yang mempunyai algoritma pada DTM dengan kompleksitas waktu p(n), yaitu polinomial terhadap besar input. Kelompok problem P merupakan subset dari kelompok problem NP.
- Kelompok problem NP-Sukar (NP-Hard): Problem komputasi yang setidaknya sama sukarnya dengan semua problem NP lain. Karenanya secara teoretis setiap instan problem NP dapat dikonversi menjadi instan salah satu problem NP-Sukar.
- Kelompok problem NP-Sempurna (NP-Complete): Problem komputasi yang tergolong NP dan sekaligus NP-Sukar. Implikasinya adalah ada problem komputasi yang tergolong NP-Sukar tetapi tidak NP-Sempurna.
- P=NP?: Suatu pertanyaan besar di dunia Informatika: Apakah semua problem NP juga P. DPL, apakah setiap problem NP dapat mempunyai algoritma waktu polinomial pada DTM atau pada mesin RAM? Atau mungkinkah salah satu problem yang tergolong NP-Sempurna diselesaikan dalam waktu p(n)?
- Kemampuan komputasi: Kemampuan untuk menyelesaikan (baca: adanya algoritma untuk) suatu problem komputasi. Suatu problem komputasi mungkin dapat diselesaikan pada suatu model komputasi, tetapi belum tentu dapat diselesaikan pada model yang lain. Suatu problem komputasi dapat diselesaikan dalam waktu t(n) pada suatu model, mungkin dapat diselesaikan dalam waktu t(p(n)) untuk model yang lain atau t(exp(n)) oleh model yang lain lagi.
- Algoritma efisien dan solusi dalam waktu polinomial: Algoritma adalah susunan instruksi solusi problem komputasi. Hasil dari algoritma dapat diperoleh setelah eksekusi algoritma berakhir. Algoritma dikatakan efisien jika waktu eksekusinya terbatas polinomial terhadap besar input, O(p(n))
- Problem Optimasi: Problem komputasi yang mencari nilai terbaik (optimum) dari semua kemungkinan nilai optimal yang ada. Contoh: mencari nilai terkecil dari sejumlah data.
- Problem Pencarian dan Keputusan: Problem komputasi yang mencari apakah ada data tertentu yang memenuhi kriteria / batasan yang diberikan. Contoh: mencari suatu data x dari sejumlah data.
- Instan suatu problem: Aktualisasi dari deskripsi problem komputasi, biasanya merupakan satu set lengkap input untuk problem tersebut. Contoh data {20, 2, 7, 30} adalah instan problem sorting dengan ukuran input n=4 data.
- Sertifikat suatu problem: Suatu data yang dapat digunakan untuk memeriksa kebenaran instan suatu problem pencarian/keputusan. Contoh diatas dapat diberikan sertifikat {2, 7, 20, 30}.
- Verifikasi solusi: Diberikan pasangan (instan, sertifikat), verifikasi adalah proses memeriksa kebenaran sertifikat tersebut. Waktu proses verifikasi sertifikat problem NP tidak boleh lebih dari p(n) (karena output instan problem NP dapat diperoleh dalam waktu p(n) pada NDTM).
- Polinomial, Super-polinomial, Sub-eksponensial, dan Eksponensial: Problem komputasi dapat dikelompokan kedalam beberapa kelas tergantung kompleksitas solusi terbaik yang dimilikinya; Misal untuk input data sebesar n, O(n4) adalah polinomial, ω(nlg(n)) adalah super-polinomial, ο(2lg(n)) adalah sub-eksponensial, dan O(1.4142n) adalah eksponesial.
One response to “Berbagai Catatan Seputar NP-Sempurna”
Thanks a lot for shared the knowledge..