Bertahun lalu, ketika awal adanya komputer, orang-orang mulai membuat mesin yang simpelnya bisa berhitung. Mikirnya begini, kalo komputer bisa lebih cepat kenapa gak pake komputer aja? Jadi dipakai komputer buat menghitung persamaan-persamaan differensiasi, integral, transformasi, diskrit, dan lainnya. Tapi dulu komputer buat ngitung kayak gituan butuh waktu lama buat mencari jawabannya, dan seiring waktu ternyata komputer yang semakin berkembang malah mempercepat proses perhitungan.

Komputer kalau diberi tugas perkalian, pengurangan, penambahan, pembagian, dan pengurutan deret ternyata akan semakin cepat dengan semakin bagusnya komputer.

Tapi nyatanya, ada beberapa problem yang gak bisa berjalan cepat untuk cari jawabannya. Salah satu contohnya adalah masalah ‘salesman keliling.’

Masalah ini sering disebut sebagai optimatisasi untuk mencari biaya termurah dan optimal untuk para sales. Masalah ini tidak bisa diselesaikan dengan cepat, karena terlalu banyak faktor yang mempengaruhi seperti tiket pesawat, biaya makan, biaya hotel, dan lain-lain.

Disini dimana orang-orang mulai mengelompokkan berbagai permasalahan, mana yang cepat diselesaikan,dan mana yang memang lama untuk diselesaikan oleh komputer. Dan orang-orang juga mengelompokkan beberapa yang mungkin dan bisa jadi susah atau mudah.

Jadi orang masih terus berusaha, apa memang ada program yang lebih baik dan komputer berperforma tinggi yang dapat menyelesaikan masalah-masalah yang belum terklasifikasi antara cepat dan lambat.

Disinilah munculnya P dan NP.

P adalah apa yang disebut sebagai Polynomial Time (Waktu Polinomial). Artinya jumlah tahapan penyelesaian ada dalam bentuk persamaan polinomial besar masalahnya.



S adalah jumlah tahapan penyelesaian, dan N adalah besar masalahnya. f(N) adalah bentuk persamaan polinomial. Persamaan polinomial adalah seperti berikut:



Tapi bukan seperti berikut:



Maksudnya adalah, jumlah tahapan penyelesaian tidak begitu banyak dan luar biasa banyaknya jika dibandingkan dengan besarnya masalah, seperti penambahan, 1+1, tidak akan berbeda dengan 1+3240, ya kan? Sama-sama hanya satu kali jalan, tanpa merubah jumlah tahapan penyelesaian dan tidak menambah jauh waktu untuk penyelesaian.

Sedangkan NP adalah Non-Deterministic Polynomial Time (Waktu Polinomial Non-Deterministik). Ini adalah bentuk non deterministik dari P, dimana kita akan mencari seberapa banyak kemungkinan jawaban yang benar dari waktu polinomial. Tentu ini akan memakan banyak waktu karena jawabannya tidaklah deterministik dan memiliki banyak kemungkinan. Ini layaknya masalah mencari jawaban ‘trial dan error’ ketika memecahkan masalah faktorisasi persamaan kuadrat atau mungkin... Sudoku?

Jadi ya, melihat beberapa sumber, memang lebih enak menjelaskannya dari puzzle seperti sudoku.

Sepertinya P dan NP hanyalah sebuah daya tarik yang mendasar dari berbagai macam hirarki kesulitan kompleksivitas dalam komputasi. P dan NP hanya memberi sebagian kecil dari apa yang akan menjadi sebuah ‘Kebun Kompleksivitas’.

P dan NP adalah sebuah permulaan.

P dan NP rupanya hanya sebagian kecil dari kebun kompleksivitas. Di NP, terdapat sebuah kelompok yang disebut sebagai NP-Komplit. Bisa dibilang NP-komplit adalah bagian tersulit dari NP. Di dalam NP-komplit ada yang disebut dengan NP-sulit atau NP-hard. Istilah ini merujuk pada problem-problem dengan tingkat kesulitan NP yang sangat tinggi. Beberapa diantaranya adalah masalah kepuasan, pencocokan 3-dimensi, hingga pengaturan jadwal kerja.


Apabila agan bisa menemukan sebuah mesin yang bisa menyelesaikan masalah setidaknya salah satu yang disebutkan dengan cepat, maka mesin itu bisa menyelesaikan seluruh permasalahan dalam NP, sehingga seluruh sistem NP kolaps menjadi P, maka P=NP! Namun apabila memang tidak ada mesin yang cepat untuk masalah NP-sulit, maka P≠NP. Jadi ya sampai sekarang masih belum ada yang tahu, semua orang masih mencoba.



Tak berhenti disitu, di dalam P, masih ada kelompok NL atau Non-deterministic Logarithmic Space (Ruang Logarithmik Non-deterministik) dan di dalamnya ada L atau Logarithmic Space (Ruang Logaritmik). Dan di dalam L masih ada AC atau Alternating Class.
Diluar NP ada EXP atau Exponential Polinomial. Disini adalah tempat dimana puzzle jadi kurang bermutu, seperti apa langkah terbaik untuk memenangkan Catur?



Jawabannya adalah tidak tahu. Karena siapa yang tahu, untuk melakukan satu kali gerakan saja bisa dibalas untuk ribuan kemungkinan yang bisa terjadi. Komputer pun akan kesakitan untuk memikirkannya karena perhitungannya terlalu besar dan luas!

Disamping NP ada yang namanya Co-NP. Co-NP adalah kelompok masalah yang berhubungan dengan Tautologi atau sebuah pernyataan yang menyatakan kalimat betul untuk semua premis yang terjadi dalam suatu peristiwa.

Di dalam EXP namun diluar NP ada sebuah kelompok masalah yang disebut PSPACE atau Polinomial Space dimana salah satu masalah yang menyangkut ruang dalam polinomial seperti permainan dibawah.

Di dalam PSPACE masih ada BPP dan BQP dan di luar dari EXP masih ada hirarki yang lebih besar lagi, seperti EXPSPACE dan diatasnya masih ada lagi 2-EXP dan terus hingga kelompok tertinggi ke masalah penentuan (Decideable) dan hingga ke masalah pelimitan.



Memang ternyata kompleksivitas masih rumit dari yang dipikirkan. Masih ada pertanyaan seperti NP vs. Co-NP, L vs. NL, dan sebagainya. Sepertinya untuk NP dan P adalah fokus utama untuk para ilmuwan kompleksivitas saat ini.