Bayangkan jika suatu hari kita ingin mengunjungi situs yang lama tidak kita tengok. Situs ini memerlukan pendaftaran pengguna dimana kita harus memasukkan nama pengguna (user name) dan password. Karena sudah terlalu lama tidak dipakai, mungkin kita masih ingat nama pengguna tetapi lupa pada password-nya. Tetapi kita punya kebiasaan bahwa untuk membuat password, kita selalu memakai kombinasi dari bilangan favorit kita, yaitu 1, 3, 5, 7, dan 9, lalu disambungkan dengan nama depan dari kucing kita. Seandainya situs ini memperbolehkan pengguna untuk mencoba password sebanyak yang kita mau, berapa kali kita harus mencoba hingga berhasil masuk situs ini? Jika waktu mengetik sampai dengan mendapat tanggapan dari situs perlu waktu 1 menit, berapa lama kita harus menunggu?
Cerita diatas adalah gambaran dari permasalahan kombinatorial. Untuk kasus sederhana ini, kita akan mencoba menghitung kondisi terburuk (worst case), yaitu jumlah maksimum kita mencoba-coba kombinasi berbagai password hingga dapat masuk ke situs. Andaikan kita tidak pernah lupa nama depan dari kucing kesayangan kita, maka banyaknya usaha yang kita perlukan adalah sejumlah permutasi dari 5 angka ini, yaitu 5!=5.4.3.2.1 = 120 kali. Dengan demikian, waktu yang diperlukan (maksimum) sampai kita bisa masuk situs adalah 2 jam.
Bayangkan jika ternyata seluruh 10 dijit angka yang ada, yaitu 0, 1, …, 9, ini kita pakai (karena semuanya favorit), maka kita perlu waktu sebanyak 10! Dengan memakai hampiran Stirling n!~sqrt(2*PI*n)(n/e)n, dimana PI~3.1416… dan e ~ 2.7183 …, angka ini kira-kira sebesar 3.6*106. Dengan demikian kita kita harus menunggu didepan komputer selama lebih kurang 6.8 tahun.
Sebagai catatan, seorang peretas (hacker) mungkin bisa masuk dengan cara yang lebih cepat karena punya trik lain, tetapi ini bukan pokok bahasan kita saat ini.
Perhitungan seperti ini, yakni berapa langkah suatu algoritma/proses perlu dijalankan hingga jawaban ketemu disebut sebagai kompleksitas perhitungan (computational complexity). Didalam teori kompleksitas, jumlah langkah absolut atau waktu proses absolut kurang begitu penting. Justru yang lebih penting lagi adalah pertumbuhan lama proses seiring dengan membesarnya masukan. Contoh diatas menggambarkan, penambahan masukan yang hanya duakali mengakibatkan kita menunggu sekitar 30.000 ribu kali lebih lama.
Fungsi pertumbuhan dilambangkan sebagai O(..), yang dibaca “big-Oh”. Contoh diatas termasuk dalam kategori O(n!), suatu masalah yang sangat sulit atau hard problems. Algoritma yang tumbuh eksponensial O(en) juga masuk kategori hard. Disamping itu, ada masalah-masalah lain yang lebih mudah. yang dikategorikan sebagai masalah ber-kompleksitas polinomial atau P Problems. Dengan demikian pertumbuhannya adalah O(nk), dimana k konstanta.
Salah satu masalah fundamental didalam ilmu komputer adalah, apakah hard problems (kombinatorial maupun eksponensial) dapat diubah menjadi masalah dengan kompleksitas polinomial? Sebagai gambaran, FFT (Fast Fourier Transform) yang merupakan satu dari sepuluh algoritma terbaik abad ini karena berhasil merevolusi dunia elektronika dijital, “hanya” mengubah penghitungan transformasi Fourier diskrit (DFT) dari O(n2) menjadi O(n*log(n)). Berikut ini adalah dua contoh lain dari hard problems:
- HCP (Hamiltonian Cycle Problem). Seorang salesman ingin mempromosi kan dagangannya ke n buah kota, masing-masing hanya boleh sekali dikunjungi, kemudian harus kembali ke tempat semula. Bagaimana rute yang harus dilalui supaya ongkos-nya paling murah (atau jarak yang ditempuh-nya paling pendek)? Masalah ini disebut sebagai TSP (Traveling Salesman Problem). Jawaban eksak dapat diperoleh dengan cara mendaftarkan seluruh kemungkinan lintasan (Hamiltonian Circuit), yakni sebanyak n!/2, kemudian merangking yang paling murah (pendek). HCP lebih sederhana lagi tapi punya tingkat kesulitan setara. Dalam teori graf, kota-kota yang dikunjungi disebut vertex, sedangkan jalur perjalanan (rel KA, jalan raya, atau rute pesawat terbang) disebut edge. Diberikan suatu graf G=(V,E) , dimana V kumpulan vertex dan E kumpulan edge, adakah sirkit Hamilton didalam G?
- Subset Sum. Diberikan suatu himpunan bilangan, misalnya S={1, 2, 3, 6}. Adakah partisi yang tak beririsan, sebut saja S1 dan S2, sehingga jumlah bilangan dalam setiap partisi sama? Jawaban eksak dapat dicapai dengan mendaftarkan seluruh pasangan himpunan tak beririsan, kemudian memeriksa satu persatu; misalnya {1, 2 } dan {3,6}, {1,3, 6} dan {2} … dst.
Pernah mendengar bagaimana prinsip kerja dari enkripsi RSA? Metoda penyandian ini memanfaatkan sulitnya melakukan pemecahan suatu bilangan bulat komposit menjadi faktor-faktor primanya. Tentu kalau bilangan bulat ini kecil, misalnya 10, kita dengan cepat bisa menemukan faktor primanya yaitu 2 dan 5. Sebaliknya, jika bilangan ini besar, katakan sampai 128 dijit, tentu sulitnya bukan main. Disisi lain, jika kita ketahui salah satu faktornya, dengan cepat kita bisa menghitung faktor yang lain. RSA memanfaatkan prinsip ini; jika kita punya kuncinya, maka kita akan bisa membuka enkripsinya dengan mudah.
Kedua masalah diatas mirip dengan prinsip kerja RSA. Pada HCP, jika kita diberikan urutan dari sekumpuan vertex, dengan mudah dapat diperiksa apakah urutan ini menyatakan sirkit Hamilton dari graf G atau bukan (hanya dengan menyusuri setiap verteks dalam daftar sesuai urutan). Demikian pula pada Subset Sum, Jika kita diberikan S1 = {1, 2, 3} dan S2 = {6}, dengan mudah bisa dipastikan bahwa partisi ini memenuhi syarat. Hal yang sebaliknya tidak mudah, tentu untuk kasus umum dimana jumlah anggota bisa berapapun. Kedua solusi tadi, yaitu sirkit Hamilton dan subset S1 dan S2 disebut certificate.
Dua masalah diatas merupakan contoh dari permasalahan yang disebut sebagai NP-Complete Problems (NP-Nondeterministic Polynomial), yang diformulasikan oleh Stephen Cook dalam makalah-nya, “The Complexity of Theorem Proving Procedures” yang terbit pada tahun 1971. Kemudian Richard M. Karp menemukan adanya 21 buah masalah yang bersifat demikian. Hebatnya lagi, seluruh masalah yang disebut NP-Complete ini setara, yang satu dapat direduksi dari yang lain. Kita bisa menerjemahkan satu masalah ke masalah lain dengan suatu transformasi (yang dapat dilakukan secara polinomial juga), sehingga jika salah satu bisa dipecahkan dengan kompleksitas polinomial, maka yang lain dengan sendirinya juga bisa. Seperti efek domino, begitu satu dari NP-Complete problems ini “jatuh”, seluruh masalah yang masuk kategori NP-Complete akan terpecahkan. Hasil ini ditulis dalam makalah seminalnya yang berjudul “Reducibility Among Combinatorial Problems” Oleh penemuan dan pengembangan bidang ini, Cook mendapatkan Turing Award pada tahun 1982, sedangkan Karp mendapatkannya pada tahun 1985. Turing Award bisa dianggap sebagai Hadiah Nobel dalam bidang computing.
Pada tahun 2000, Clay Mathematics Institute menawarkan hadiah sebesar 1 Juta Dollar kepada siapa saja yang dapat menjawab salah satu dari 7 buah permasalahan yang disebut sebagai Millenium Prize Problems, dimana salah satunya menanyakan apakah P = NP? Jika sama, dampaknya tentu sangat besar sekali. Jika seseorang dapat memecahkan permasalahan HCP dalam waktu polinomial, para ahli transportasi maupun perancang PCB (Printed Circuit Board) akan sangat terbantu. Hingga kini, orang hanya bisa mendekati solusi optimal dari masalah ini, terutama dengan memanfaatkan randomized algorithm. Sebagian besar ilmuwan cenderung mengatakan bahwa P tidak sama dengan NP, tetapi beberapa diantaranya yakin bahwa P=NP. Yang jelas, hingga kini belum ada seorangpun yang tahu jawabannya.
