menampilkan hal-hal unik dalam dunia kita !

Isu vs merupakan isu klasik paling terkenal dalam dunia Computer Science dan Riset Operasi yang belum terjawab hingga saat ini. Sejak awal tahun 1970, sudah banyak orang yang menghabiskan waktu untuk memikirkannya, namun sulit untuk mengatakan bahwa isu itu telah terjawab tuntas.

Hal itu terekam dalam jajak pendapat^[1] yang dilakukan oleh William I. Gasarch dari Universitas Maryland, USA, di tahun 2002. Dari 100 orang, 61 menjawab dan hanya 9 orang yang menjawab . Sementara 22 orang tidak memberi jawaban. Yang menarik, 5% menjawab bahwa isu ini tidak akan pernah terselesaikan.

Sebenarnya isu apakah vs ini ?

Semuanya berawal ketika Alan Turing^[2] memperkenalkan Turing machine, yang selanjutnya menjadi model komputer standar dalam computability theory.

Secara informal, kelas merupakan kelas dari decision problems yang terselesaikan oleh beberapa algoritma dalam sejumlah langkah yang dibatasi oleh beberapa polinomial tetap dalam panjang inputan^[3]. Turing memang tidak berfokus pada efisiensi, tapi pada apakah mesin-mesinnya dapat mensimulasi sebarang algoritma dalam waktu yang cukup.

Sementara merupakan singkatan dari “Nondeterministic Polynomial time“, karena awalnya didefinisikan berkenaan dengan nondeterministic machines, yakni mesin-mesin yang memiliki lebih dari satu kemungkinan bergerak dari konfigurasi yang diberikan^[3].

Selanjutnya, gagasan perhitungan polynomial-time diperkenalkan pada tahun 1960-an oleh Cobham ^[4] dan Edmonds ^[5] sebagai bagian dari perkembangan awal teori kompleksitas komputasional, walaupun sebelumnya von Neumann ^[6] pada tahun 1953 telah membedakan antara algoritma polynomial-time dan exponential-time.

Tahun 1971, Stephen Cook dan Leonid Levin, secara terpisah, memformulasikan isu vs ini^[7]. Clay Mathematics Institute (CMI) membahasakan persoalan sebagai easy to find dan persoalan sebagai easy to check.

CMI memberikan sebuah contoh untuk memudahkan pemahaman. Misalkan Anda diberi tanggung jawab untuk mengatur akomodasi dari 400 mahasiswa. Karena keterbatasan tempat, hanya 100 yang dapat tinggal di asrama. Untuk memperumit masalah, Dekan memberi Anda sebuah daftar nama-nama mahasiswa bermasalah, dan meminta agar tak ada satu nama pun dari daftar ini yang boleh muncul dalam keputusan akhir Anda.

Contoh ini merupakan contoh di mana para computer scientist menyebutnya sebagai persoalan karena mudah untuk memeriksa apakah 100 orang yang terpilih itu sudah sesuai dengan permintaan Dekan, yang artinya tidak ada satu nama pun dari daftar Dekan yang masuk ke dalam 100 nama orang pilihan tersebut.

Namun membuat kombinasi 100 nama dari 400 pelamar itu sungguh sulit. Bahkan total jumlah kombinasinya melebihi jumlah atom di alam semesta. Karenanya tidak dapat diharapkan adanya supercomputer sekalipun yang mampu menyelesaikannya secara brute force, yakni memeriksa setiap kombinasi yang mungkin dari 100 mahasiswa.

Satu masalah yang ada dalam computer science adalah menentukan apakah sebuah pertanyaan memiliki jawaban yang dapat diperiksa secara cepat, namun membutuhkan waktu yang sangat lama utuk menyelesaikannya melalui berbagai cara langsung. Contohnya seperti pemilihan 100 dari 400 mahasiswa itu. Apakah benar tidak ada cara yang layak untuk menghasilkan sebuah jawaban dengan bantuan komputer ?

Untuk keperluan itu, CMI menyediakan dana 1 juta US$ sebagai hadiah !

Meski sebagian besar computer scientist percaya bahwa , sebagaimana tercermin pada hasil jajak pendapat^[1], kronologi^[8] yang disusun oleh G.J. Woeginger menunjukkan persaingan yang seimbang.

Kronologi dimulai oleh Ted Swart (University of Guelph), 1986-7, yang menyatakan melalui beberapa artikelnya yang menjabarkan formulasi Linear Programming berukuran polinomial untuk permasalahan siklus Hamiltonian. Karena Linear Programming dapat dipecahkan secara polinomial, sementara siklus Hamiltonian merupakan -hard, maka Swart berkesimpulan bahwa .

Kronologis berlanjut hingga pembuktian terbaru yang disodorkan oleh Vinay Deolalikar (HP Labs), Agustus 2010, yang mendukung . Deolalikar menggunakan finite model theory, sebuah area logika, untuk menyimpulkan struktur dalam random satisfiability problem.

Namun demikian, banyak pihak yang meragukan kevalidan bukti ini, salah satunya Michael Trick^[9], profesor Riset Operasi senior dari Carnegie Mellon University yang pernah menjabat sebagai Presiden INFORMS dan Wakil Presiden IFORS. Bahkan Scott Aaronson, associate professor dari MIT, berani bertaruh akan menghipotekkan rumahnya dan chip senilai 200 ribu US$, jika pembuktian yang disodorkan Deolalikar itu terbukti benar^[10].

Dan isu pun masih tetap terbuka, paling tidak, hingga saat artikel ini selesai dituliskan.