Misteri Matematika yang Menghubungkan Sudoku, Jadwal Penerbangan, dan Pelipatan Protein

Ilmu komputer tampaknya mengalami kemajuan yang tidak dapat dihentikan. Beberapa dekade saja membawa kita dari tabung vakum ke microchip, dial-up ke Internet berkecepatan tinggi dan Office Assistant Clippy ke ChatGPT. Namun ribuan masalah sehari-hari di bidang sains dan industri masih belum dapat dipecahkan oleh armada superkomputer bertenaga AI saat ini.

Masalah “NP-complete” yang terkenal sulit ini menjanjikan hadiah jutaan dolar, yang diberikan oleh lembaga nirlaba Clay Mathematics Institute, baik untuk menemukan solusi cepat atau membuktikan bahwa tidak ada solusi yang ada. Pemahaman luar biasa dari tahun 1970an menjadikan tantangan ini semakin menarik: ribuan lebih masalah tersebut, dalam arti yang mendalam, adalah satu dan sama. Jika Anda menyelesaikan satu, Anda menyelesaikan semuanya. Konsep ini, yang sekarang menjadi dasar bidang ilmu komputer teoretis, menunjukkan bahwa kelompok masalah komputasi tertentu membentuk suatu jaringan terpadu. Temukan algoritme cepat yang memecahkan teka-teki Sudoku dalam ukuran berapa pun, dan kini Anda dapat memecahkan skema enkripsi yang melindungi ekonomi digital kita. Temukan pintasan untuk menjadwalkan tur penerbangan sesuai anggaran, dan Anda dapat menggunakannya untuk menyelesaikan hampir semua soal matematika terbuka yang terkenal.

Menemukan algoritma yang cepat untuk masalah NP-complete ini (atau membuktikan bahwa tidak ada algoritma seperti itu) akan menyelesaikan pertanyaan “P versus NP”, yang merupakan misteri paling penting dalam ilmu komputer. P mengacu pada kumpulan masalah komputasi yang dapat diselesaikan komputer secara efisien. Sedangkan NP adalah singkatan dari permasalahan yang solusinya dapat dilakukan diverifikasi secara efisien. Namun permasalahan tersebut belum tentu bisa diselesaikan dengan cepat. NP mencakup semua yang ada di P (karena menemukan solusi adalah cara yang sangat baik untuk memverifikasinya) tetapi juga masalah yang lebih sulit yang kita tidak tahu metode efisiennya. temuan solusi. Kami hanya dapat memverifikasinya setelah masalah tersebut diselesaikan. Pertanyaan P versus NP menanyakan apakah asimetri yang tampak antara menemukan solusi dan memverifikasi solusi itu nyata atau hanya ilusi. Mungkin P = NP, dan keduanya merujuk pada rangkaian masalah yang sama. Dengan kata lain, mungkin masalah NP yang kita tidak tahu cara menyelesaikannya secara efisien saja muncul relatif sulit terhadap masalah P karena kami belum menemukan wawasan yang tepat.

Tentang mendukung jurnalisme sains

Jika Anda menikmati artikel ini, pertimbangkan untuk mendukung jurnalisme pemenang penghargaan kami dengan berlangganan. Dengan membeli langganan, Anda membantu memastikan masa depan cerita yang berdampak tentang penemuan dan ide yang membentuk dunia kita saat ini.

Misalnya, apakah ada algoritme (resep instruksi sederhana) yang, dengan banyaknya daftar kota, penerbangan penghubungnya, dan anggarannya, akan secara efisien memutuskan apakah Anda dapat mengunjungi semuanya dengan tetap memperhatikan anggaran? Kami tidak tahu. Kami tahu sebuah tidak efisien algoritma: periksa setiap kemungkinan urutan penerbangan yang mengunjungi semua kota, jumlahkan biaya masing-masing kota, dan bandingkan totalnya dengan anggaran. Namun seiring dengan bertambahnya jumlah kota dalam daftar, jumlah rute untuk melakukan pemeriksaan pun meledak secara eksponensial, dan dengan cepat menjadi tidak mungkin dilakukan bahkan untuk komputer tercepat sekalipun. Mungkin ada atau tidak ada jalan pintas cerdas yang dapat menghindari pencarian menyeluruh ini, namun para ilmuwan komputer belum menemukannya. Diberikan a larutanNamun—dalam hal ini, daftar penerbangan yang diusulkan—seseorang dapat memverifikasi dalam jangka waktu yang wajar apakah suatu rute menjangkau setiap kota dan tetap sesuai anggaran. Jika P sama dengan NP, berarti skenario penerbangan (contoh dari apa yang disebut masalah penjual keliling) mempunyai penyelesaian yang cepat. Kami hanya belum mengetahuinya.

Banyak masalah komputasi alami yang bergabung dengan masalah penjual keliling di himpunan NP. Hal ini mencakup tantangan dari bidang logistik (seperti mengemas kotak ke dalam truk), jejaring sosial (menemukan kelompok teman bersama), biologi (memprediksi bagaimana protein akan terlipat), dan permainan seperti Sudoku, Pokémon, dan Candy Crush. Kita bahkan dapat menjadikan matematika itu sendiri sebagai soal NP karena pembuktiannya dapat diverifikasi secara efisien. Mungkin terasa aneh untuk mengklasifikasikan ini sebagai masalah “sulit” ketika orang mengemas kotak ke dalam truk dan memecahkan Sudokus setiap hari. Namun kami menganggap suatu algoritma telah memecahkan masalah secara efisien hanya jika itu terpecahkan setiap misalnya secara efisien, termasuk yang sangat besar. Tentu saja, komputer dapat menyelesaikan Sudoku 9×9 lebih cepat daripada satu juta x juta Sudoku, jadi definisi ketat tentang “efisien” mengacu pada bagaimana waktu yang diperlukan untuk menyelesaikan suatu masalah berskala sesuai dengan ukuran inputnya.

Pertanyaan P versus NP berkaitan dengan berbagai masalah komputasi dan keterkaitannya satu sama lain, sehingga penyelesaiannya mungkin memerlukan penyelidikan masing-masing masalah tersebut satu per satu. Katakanlah Anda menemukan algoritma yang efisien untuk masalah tenaga penjualan keliling. Ini akan menjadi terobosan yang heroik, tetapi apakah ini memberi tahu Anda tentang kemampuan Anda memecahkan Sudokus besar atau masalah NP menantang lainnya? Hebatnya, algoritme Anda untuk satu masalah itu akan menyelesaikan P versus NP sepenuhnya. Pada tahun 1972, ilmuwan komputer Richard Karp menerbitkan makalah penting yang menunjukkan bahwa 21 masalah NP klasik memiliki sifat yang luar biasa: algoritma yang efisien untuk menyelesaikan salah satu dari masalah tersebut dapat digunakan tidak hanya untuk menyelesaikan 20 masalah lainnya tetapi juga untuk menyelesaikannya. setiap masalah di NP. Dia menyebut 21 masalah ini NP-lengkap. Pada tahun-tahun berikutnya, daftar tersebut bertambah seiring para peneliti menemukan banyak masalah NP lain yang memiliki sifat ajaib ini (termasuk masalah penjual keliling).

Kita bisa melihat kelengkapan NP dengan optimisme atau pesimisme. Di sisi optimis, benteng permasalahan yang sangat sulit yang menghalangi kita dan janji teknologi yang tak terhitung kini lebih terlihat seperti rumah kartu. Tariklah satu hal ke dalam bidang kelayakan dan seluruh bangunan NP akan runtuh, dan revolusi ilmiah akan bangkit dari puing-puing, diisi dengan perjalanan yang efisien dan mudah, penemuan obat yang cepat melalui pelipatan protein, dan era baru matematika. Di sisi pesimistis, kelengkapan NP menunjukkan bahwa masalah ini tidak memiliki algoritma yang efisien; jika semua yang diperlukan untuk membuktikan sebaliknya berarti mengatasi satu masalah, lalu mengapa belum ada yang berhasil? Kebanyakan ahli condong pada interpretasi terakhir dan menduga bahwa masalah NP-complete tidak memiliki algoritma yang cepat.

Baik dilihat dari gelas setengah penuh atau setengah kosong, konsep masalah lengkap mengubah cara peneliti memandang komputasi. Karp menunjukkan bahwa ia dapat menggunakan suatu algoritma untuk suatu permasalahan NP-complete untuk menyelesaikan permasalahan lainnya dengan terlebih dahulu mendemonstrasikan bahwa Anda dapat menerjemahkan permasalahan yang tampaknya tidak berhubungan ke dalam bahasa masing-masing menggunakan proses yang disebut a pengurangan. Cara kerjanya adalah dengan menunjukkan cara mengambil contoh dari satu soal (misalnya yang melibatkan daftar kota, penerbangan antarkota, dan anggaran) dan mengubahnya menjadi soal lain (misalnya teka-teki Sudoku besar) sedemikian rupa sehingga Sudoku hanya memiliki solusi valid jika memungkinkan untuk mengunjungi semua kota sesuai anggaran (dan sebaliknya tidak memiliki solusi valid). Dengan begitu, jika Anda menemukan algoritme yang efisien untuk Sudoku, Anda juga dapat menggunakannya untuk memecahkan masalah tenaga penjual keliling dengan mengubah contoh algoritma tersebut menjadi teka-teki Sudoku. (Lihat bagian bawah cerita ini untuk contoh keren pengurangan detail lengkap.)

Kemampuan untuk menyandikan satu masalah menggunakan bahasa lain bukan hanya kekhasan dari contoh ini tetapi juga merupakan fitur komputasi itu sendiri. Jaringan reduksi menyatukan semua masalah NP-complete. Selesaikan salah satunya, dan Anda dapat menyelesaikan masalah NP lainnya. Implikasinya mengejutkan pikiran. Ingat kita dapat membingkai pembuktian teorema matematika sebagai masalah NP-lengkap. Pilih pertanyaan matematika terkenal yang belum terpecahkan. Teori kelengkapan NP kemudian memberi tahu kita bahwa ada beberapa level Candy Crush yang secara sempurna mengkodekan pertanyaan matematika Anda. Jika skor tertentu dapat dicapai dalam sejumlah gerakan tertentu pada level Candy Crush tersebut, maka soal matematika Anda memiliki bukti dengan jangka waktu tertentu; jika tidak maka tidak. Kelengkapan NP juga meyakinkan kita bahwa kemajuan tertentu dalam pelipatan protein (atau pengemasan kotak atau penyelesaian Sudoku) akan menghancurkan ekonomi digital. Itu karena enkripsi yang melindungi data sensitif kami bekerja dengan menyembunyikannya di balik masalah komputasi yang diyakini sulit diselesaikan. (Perlu dicatat bahwa meskipun menyelesaikan masalah NP-complete akan memungkinkan Anda memecahkan enkripsi, hal sebaliknya tidak benar; masalah sulit yang mendasari sebagian besar skema enkripsi tidak sepenuhnya NP-complete.)

Dengan semua masalah NP-complete ini, satu juta dolar mungkin tampak seperti tawaran yang murah untuk solusinya. Dan ini mungkin menawarkan sedikit motivasi tambahan saat Anda kesulitan menjadwalkan perjalanan liburan atau memecahkan teka-teki Sudoku.

Bagaimana Cara Kerja Pengurangan?

Bagi siapa pun yang ingin mendalami cara kerja reduksi, mari kita kurangi jenis masalah NP-complete yang lain, yaitu “masalah peta tiga warna”, menjadi “masalah klik”. Masalah tiga warna peta menanyakan: Dengan adanya sebuah peta, dapatkah Anda menetapkan salah satu dari tiga warna untuk setiap wilayah sehingga tidak ada wilayah tetangga yang mengulangi suatu warna? Masalah klik malah bertanya: Dengan adanya jaringan sosial, apakah jaringan tersebut berisi sekelompok orang dengan jumlah tertentu yang semuanya merupakan teman bersama? Kedua permasalahan tersebut adalah NP-complete, artinya kita tidak mengetahui algoritma yang efisien untuk keduanya. Di permukaan, mereka tidak punya banyak kesamaan. Namun kami akan menunjukkan bahwa dengan adanya peta, kita dapat mengubahnya menjadi jaringan sosial sedemikian rupa sehingga jawaban terhadap masalah jaringan sosial akan memberikan kita jawaban terhadap masalah peta.

Bayangkan peta AS. Untuk membangun jejaring sosial, kami akan menunjuk tiga “orang” untuk setiap negara bagian, satu untuk masing-masing tiga warna: biru, hijau dan merah. Kami kemudian akan membuat dua orang menjadi teman kecuali:

1. Mereka mewakili negara bagian yang sama. (Perwakilan Wisconsin yang berwarna hijau tidak akan berteman dengan perwakilan Wisconsin yang berwarna biru.)

2. Mereka memiliki warna yang sama dan mewakili negara-negara tetangga. (Dakota Utara dan Dakota Selatan berbagi perbatasan, sehingga perwakilan merah mereka tidak akan berteman, namun Dakota Utara dan Florida tidak, sehingga perwakilan merah mereka akan menjadi teman.)

Saya mengklaim bahwa jejaring sosial yang terdiri dari 150 orang ini akan berisi klik yang terdiri dari 50 teman bersama hanya jika peta AS memiliki tiga warna yang valid. Jika kami menemukan 50 teman yang sama dalam jaringan, mereka semua harus mewakili negara bagian yang berbeda karena, sesuai desain, kami tidak membuat orang menjadi teman ketika mereka mewakili negara bagian yang sama. Selain itu, pewarnaan yang sesuai dengan klik tidak akan pernah memberikan warna yang sama pada negara bagian tetangga—kami secara eksplisit melarang tautan semacam itu di jaringan. Jadi, satu klik yang terdiri dari 50 orang akan menghasilkan tiga warna yang valid. Demikian pula, jika tidak ada 50 klik di jaringan, maka tidak ada tiga warna untuk peta tersebut.

Kami hanya berkurang masalah peta tiga warna ke masalah klik. Ini berarti jika seseorang menemukan algoritma cepat untuk masalah klik, maka mereka dapat menggunakannya untuk menyelesaikan masalah tiga warna peta apa pun. Yang terpenting, langkah pertama—mengubah peta menjadi jaringan—dapat dilakukan dengan cepat. Menciptakan orang-orang dalam jaringan dan hubungan persahabatan yang sesuai tidak memerlukan pencarian menyeluruh atau biaya komputasi lain yang tidak mungkin dilakukan. Pengurangan menunjukkan bahwa meskipun masalah kita terasa unik, masalah tersebut mungkin lebih bersifat universal daripada yang terlihat.

Ini adalah artikel opini dan analisis, dan pandangan yang diungkapkan oleh penulis atau penulis belum tentu merupakan pendapatnya Amerika Ilmiah.