- sponsor -

Korancrypto.com – Dilansir dari Gizmodo, Anda mungkin pernah mendengar tentang masalah P versus NP yang terkenal. Jika Anda dapat membuktikan atau menyanggah persamaan singkatnya yang samar, Anda akan menjadi sejuta dolar lebih kaya — dan bahkan mungkin miliaran dolar lebih kaya, tergantung pada keraguan Anda.

Pentingnya P versus NP terutama dalam konsekuensi untuk komputasi. Kebetulan itu adalah salah satu dari tujuh Millennium Prize Problems, yang berarti The Clay Mathematics Institute of Cambridge, Massachusetts akan memberikan US$1 juta kepada siapa pun yang berhasil membuktikan atau membantah pernyataan itu. Tetapi jika Anda membuktikan bahwa P ternyata memiliki NP yang sama, Anda bahkan tidak membutuhkan hadiah US$1 juta. Seperti yang dijelaskan oleh ilmuwan komputer teoretis Scott Aaronson pekan lalu di sebuah ceramah di auditorium pengap di Los Alamos National Lab di New Mexico, membuktikan bahwa P = NP akan membuka beberapa kemungkinan yang menarik.

“Jika seseorang membuktikan P = NP, hal pertama yang harus mereka lakukan adalah mencuri US$200 miliar dalam bitcoin. Hal kedua yang harus mereka lakukan adalah menyelesaikan semua Millennium Prize Problems lainnya,” kata Aaronson.

Untuk memahami hal ini, Anda perlu tahu bahwa komputer adalah perangkat yang menyelesaikan masalah, disarikan menjadi kode yang dapat dibaca oleh perangkat komputasi fisik, berdasarkan prinsip-prinsip yang dikemukakan oleh Alan Turing. Memecahkan masalah membutuhkan sejumlah langkah dan jumlah waktu tertentu, dengan jumlah waktu yang dibutuhkan meningkat saat masalah bertambah besar.

“P” mengacu pada masalah yang dipecahkan komputer sepanjang waktu, dari sesuatu yang sederhana seperti mengalikan dua angka menjadi tugas yang lebih kompleks seperti menjelajah internet. Ketika masalah tumbuh dalam kompleksitas, jumlah waktu yang dibutuhkan untuk menyelesaikannya tumbuh dalam “waktu polinomial.” Polinomial adalah angka dengan kekuatan dan koefisien (seperti n²). Jika suatu masalah dapat diselesaikan dalam waktu n² dan Anda menggandakan ukuran input, maka jumlah waktu yang dibutuhkan untuk menyelesaikannya akan naik empat.

Namun ada banyak masalah yang orang dapat menentukan bahwa jawaban yang diberikan benar dalam waktu polinomial, tetapi sebenarnya mendapatkan jawaban itu mungkin atau mungkin tidak dalam waktu polinomial. Ini disebut “waktu Polinomial Nondeterministik” atau masalah NP. Sudoku adalah masalah NP, yang sulit dipecahkan, mudah diperiksa. Contoh penting lainnya adalah memfaktorkan bilangan besar menjadi bilangan prima. Setidaknya untuk saat ini, dibutuhkan waktu yang sangat lama, lebih lambat dari waktu polinomial, untuk memasukkan bilangan yang sangat besar menjadi bilangan prima, tetapi memeriksa bahwa jawaban itu benar adalah semudah mengalikan angka yang dihasilkan secara bersamaan. Memang, ide yang tepat ini adalah dasar dari enkripsi modern, yang bergantung pada menghasilkan kunci keamanan yang mudah diverifikasi tetapi sulit untuk dipecahkan.

Bukti matematika yang lebih baru telah menemukan, dan mungkin terus menemukan, solusi P untuk beberapa masalah NP ini. Masalah P versus NP bertanya apakah setiap masalah NP memiliki solusi P, atau jika ada beberapa masalah NP yang benar-benar tidak dapat diselesaikan dalam P. Sepertinya jelas bahwa P tidak sama dengan NP, tetapi tidak secara ketat terbukti secara matematis. Jika Anda membuktikan bahwa P adalah sama dengan NP, Anda juga akan menunjukkan bahwa ada algoritma polinomial-waktu untuk banyak masalah komputer yang sangat penting. Anda bisa membuat diri Anda sangat kaya, penambangan bitcoin dan kunci keamanan bergantung pada masalah NP yang sulit dipecahkan dan mudah diperiksa.

Komputer kuantum, yang didasarkan pada matematika yang berbeda dari komputer klasik, tidak menjanjikan solusi P untuk setiap masalah NP. Pernah terpikir bahwa mereka mungkin dapat memecahkan kelas masalah NP yang paling sulit, yang disebut masalah NP-complete. Jika Anda dapat menemukan solusi yang efisien untuk itu, Anda akan dapat menemukan solusi yang efisien untuk semua masalah NP. Ini termasuk masalah salesman keliling dan sejumlah masalah optimasi serupa lainnya. Akan tetapi komputer kuantum belum memenuhi hype ini. Sebaliknya, komputer kuantum dapat memecahkan beberapa masalah P dalam waktu yang lebih singkat (seperti pada masalah dengan polinomial yang lebih rendah) atau memindahkan beberapa masalah NP ke dalam generalisasi kuantum P, yang disebut BQP atau “Bounded-Error Quantum Polynomial Time.”

Silakan coba dan buktikan bahwa P sama atau tidak sama dengan NP. Jika Anda berhasil, Anda akan menghasilkan setidaknya satu juta dolar, dan mungkin jauh lebih banyak. Jika Anda tidak berhasil, well, semoga Anda akan menjalani kehidupan yang bermakna dalam meneliti teori komputasi.

Sumber: Gizmodo

- sponsor -