Masalah yang Kedengarannya Mudah Menghasilkan Angka yang Terlalu Besar untuk Alam Semesta Kita | Majalah Kuanta

Jarang sekali anak usia 5 tahun dapat memahami pertanyaan-pertanyaan di garis depan ilmu komputer, namun hal ini bisa saja terjadi. Misalkan, misalnya, seorang anak taman kanak-kanak bernama Alice mempunyai dua buah apel, namun dia lebih menyukai jeruk. Untungnya, teman-teman sekelasnya telah mengembangkan sistem perdagangan buah yang sehat dengan nilai tukar yang ditegakkan secara ketat: Misalnya, tinggalkan sebuah apel, dan Anda bisa mendapatkan pisang. Bisakah Alice melakukan serangkaian perdagangan, dengan mengambil dan menurunkan pisang atau melon, sehingga dia mendapatkan buah favoritnya?

Kedengarannya cukup sederhana. “Anda bisa pergi ke sekolah dasar dan menceritakannya kepada anak-anak,” katanya Christoph Haase, seorang ilmuwan komputer di Universitas Oxford. “Orang-orang akan berpikir, 'Itu pasti mudah.'”

Namun permasalahan matematika yang mendasari dilema Alice - yang disebut masalah keterjangkauan untuk sistem penjumlahan vektor - ternyata sangat halus. Meskipun beberapa kasus dapat diselesaikan dengan mudah, para ilmuwan komputer berjuang selama hampir setengah abad untuk mengembangkan pemahaman komprehensif tentang masalah tersebut. Kini, melalui serangkaian terobosan selama beberapa tahun terakhir, mereka telah dengan tegas menetapkan betapa rumitnya masalah tersebut.

Ternyata masalah kekanak-kanakan ini tidak masuk akal, hampir seperti kartun yang rumit - begitu rumitnya hingga hampir semua masalah lainnya masalah komputasi yang terkenal sulit terlihat seperti permainan anak-anak. Cobalah untuk mengukur upaya yang diperlukan untuk memecahkan masalah ini, dan Anda akan segera menghadapi angka-angka yang begitu besar sehingga menghitung digitnya pun akan membuat Anda meraih angka-angka yang belum pernah Anda dengar. Angka-angka seperti itu sering kali mengundang perbandingan dengan skala alam semesta, tetapi analogi tersebut pun gagal. “Itu tidak adil,” katanya Georg Zetzsche, seorang ilmuwan komputer di Institut Max Planck untuk Sistem Perangkat Lunak di Kaiserslautern, Jerman. “Alam semesta ini sangat kecil.”

Dalam jangkauan?

Jika ditilik dari esensinya, masalah keterjangkauan adalah tentang objek matematika yang disebut vektor, yang merupakan daftar angka yang diurutkan. Entri dalam daftar ini disebut komponen, dan jumlah komponen dalam suatu vektor disebut dimensinya. Persediaan buah Alice, misalnya, dapat digambarkan dengan vektor empat dimensi (a, b, c, d), yang komponennya mewakili jumlah apel, pisang, melon, dan jeruk yang dimilikinya pada waktu tertentu.

Sistem penjumlahan vektor, atau VAS, adalah kumpulan vektor yang mewakili kemungkinan transisi antar keadaan dalam suatu sistem. Bagi Alice, vektor transisi (−1, −1, 1, 0) mewakili pertukaran apel dan pisang dengan melon. Masalah keterjangkauan VAS menanyakan apakah ada kombinasi transisi yang diizinkan yang dapat membawa Anda dari keadaan awal tertentu ke keadaan target tertentu — atau, dalam istilah matematika, apakah ada jumlah vektor transisi yang mengubah vektor awal menjadi vektor target. Hanya ada satu kendala: Tidak ada komponen vektor yang menggambarkan keadaan sistem yang bisa turun di bawah nol.

“Itu adalah pembatasan yang sangat wajar untuk model realitas,” kata Wojciech Czerwiński, seorang ilmuwan komputer di Universitas Warsawa. “Anda tidak bisa mendapatkan jumlah apel yang negatif.”

Dalam beberapa sistem, mudah untuk menentukan apakah vektor target dapat dijangkau. Namun tidak selalu demikian. Ilmuwan komputer paling tertarik pada sistem penjumlahan vektor yang terlihat sederhana dan tidak jelas betapa sulitnya menentukan keterjangkauan. Untuk mempelajari kasus-kasus tersebut, peneliti memulai dengan mendefinisikan angka yang mengkuantifikasi ukuran sistem tertentu. Nomor ini, diwakili oleh n, mencakup jumlah dimensi, jumlah transisi, dan faktor lainnya. Mereka kemudian bertanya seberapa cepat kesulitan masalah keterjangkauan dapat meningkat n tumbuh lebih besar.

Untuk menjawab pertanyaan itu, peneliti menggunakan dua pendekatan yang saling melengkapi. Pertama, mereka mencari contoh sistem penjumlahan vektor yang sangat rumit di mana penentuan keterjangkauan memerlukan upaya minimal. Tingkat minimum tersebut disebut “batas bawah” pada kompleksitas masalah – yang dikatakan para peneliti, “Sistem yang paling sulit untuk suatu masalah tertentu.” n setidaknya sesulit ini.”

Kedua, para peneliti mencoba untuk menetapkan “batas atas” – batasan seberapa sulit jangkauannya, bahkan dalam sistem yang paling kejam sekalipun. Ini mengatakan, “Contoh tersulit yang pernah ada n paling sulit sesulit ini.” Untuk menentukan dengan tepat seberapa sulit jangkauan dalam sistem yang paling sulit, para peneliti mencoba mendorong batas bawah ke atas dan batas atas ke bawah hingga keduanya bertemu.

Hal-hal Mimpi Buruk

Sistem penjumlahan vektor memiliki sejarah yang panjang. Sejak tahun 1960-an, ilmuwan komputer telah menggunakannya untuk memodelkan program yang memecah komputasi menjadi beberapa bagian kecil dan mengerjakan bagian-bagian tersebut secara bersamaan. “Komputasi serentak” semacam ini kini ada di mana-mana, namun para peneliti masih belum sepenuhnya memahami dasar matematisnya.

Pada tahun 1976, ilmuwan komputer Richard Lipton mengambil langkah pertama untuk memahami kompleksitas masalah keterjangkauan VAS. Dia mengembangkan prosedur untuk membangun sistem di mana cara tercepat untuk menentukan apakah suatu negara dapat dijangkau dari negara lain adalah dengan memetakan urutan transisi di antara negara-negara tersebut. Hal ini memungkinkan dia untuk menggunakan panjang jalur terpendek antara dua negara bagian yang dipilih dengan cermat sebagai ukuran kesulitan masalah keterjangkauan.

Lipton kalau begitu terbukti dia bisa membangun sistem ukuran n di mana jalur terpendek antara dua keadaan melibatkan lebih dari $lateks 2^{2^n}$ transisi. Hal ini menyiratkan adanya batas bawah eksponensial ganda pada upaya yang diperlukan untuk menentukan keterjangkauan dalam sistemnya. Ini adalah penemuan yang mengejutkan - pertumbuhan eksponensial ganda adalah mimpi buruk bagi para ilmuwan komputer. Memang benar, para peneliti sering kali menolak keras bahkan pada pertumbuhan eksponensial biasa, yang tidak ada artinya jika dibandingkan: $latex {2^5}= 32$, tetapi $latex 2^{2^5}$ lebih dari 4 miliar.

Sebagian besar peneliti mengira Lipton telah membuat sistem penjumlahan vektor yang paling rumit, yang berarti dia telah menaikkan batas bawah setinggi mungkin. Satu-satunya hal yang hilang, dalam hal ini, adalah batas atasnya — yaitu, bukti bahwa tidak mungkin ada sistem yang dapat menentukan keterjangkauan lebih sulit lagi. Tapi tidak ada yang tahu bagaimana membuktikannya. Ilmuwan komputer Ernst Mayr menjadi yang paling dekat ketika dia terbukti pada tahun 1981 yang pada prinsipnya selalu memungkinkan untuk menentukan keterjangkauan dalam sistem penjumlahan vektor apa pun. Namun pembuktiannya tidak memberikan batasan kuantitatif mengenai seberapa sulit permasalahan tersebut. Ada lantai, tapi tidak ada langit-langit yang terlihat.

“Saya tentu saja memikirkannya terus-menerus,” kata Lipton. “Tetapi setelah beberapa saat saya menyerah, dan sejauh yang saya tahu, tidak ada seorang pun yang mengalami kemajuan selama 40 tahun.”

Pada tahun 2015, para ilmuwan komputer Jérôme Leroux dan Sylvain Schmitz akhirnya didirikan batas atas kuantitatif — yang sangat tinggi sehingga para peneliti berasumsi bahwa ini hanyalah langkah pertama yang dapat didorong untuk mencapai batas bawah Lipton.

Namun bukan itu yang terjadi. Pada tahun 2019, para peneliti menemukan batas bawah yang jauh lebih tinggi daripada batasan Lipton, yang membalikkan kebijaksanaan konvensional selama beberapa dekade. Masalah keterjangkauan VAS jauh lebih kompleks daripada yang diperkirakan siapa pun.

Menara Kekuatan

Hasil mengejutkan pada tahun 2019 muncul dari kegagalan. Pada tahun 2018, Czerwiński membantah dugaan Leroux dan Filip Mazowiecki, seorang ilmuwan komputer yang sekarang berada di Universitas Warsawa, yang akan membantu mencapai kemajuan dalam masalah terkait. Dalam diskusi berikutnya, para peneliti menemukan cara baru yang menjanjikan untuk membangun sistem penambahan vektor ekstra-kompleks, yang dapat memberikan batasan baru pada masalah keterjangkauan VAS, yang kemajuannya telah terhenti begitu lama.

“Segala sesuatunya terhubung dalam pikiran saya dengan jangkauan VAS,” kenang Czerwiński. Selama satu semester dengan beban mengajar yang ringan, ia memutuskan untuk fokus secara eksklusif pada masalah tersebut, bersama Leroux, Mazowiecki dan dua peneliti lainnya — Slawomir Lasota dari Universitas Warsawa dan Ranko Lazić dari Universitas Warwick.

Setelah beberapa bulan, usaha mereka membuahkan hasil. Czerwiński dan rekan-rekannya menunjukkan bahwa mereka dapat membangun sistem penjumlahan vektor di mana jalur terpendek antara dua keadaan dihubungkan dengan ukuran sistem melalui operasi matematika yang disebut tetrasi yang membuat pertumbuhan eksponensial ganda yang mengerikan sekalipun tampak jinak.

Tetrasi adalah perpanjangan langsung dari pola yang menghubungkan operasi paling umum dalam matematika, dimulai dengan penjumlahan. Tambahkan bersama-sama n salinan suatu bilangan, dan hasilnya sama dengan mengalikan bilangan tersebut dengan n. Jika Anda mengalikannya bersama-sama n salinan suatu bilangan, yang setara dengan eksponensial, atau menaikkan bilangan menjadi nkekuatan. Tetrasi, sering kali diwakili oleh sepasang panah yang mengarah ke atas, adalah langkah selanjutnya dalam urutan ini: Tetrasi suatu bilangan dengan n berarti memperpangkatkannya n kali untuk menghasilkan menara kekuasaan n cerita yang tinggi.

Sulit untuk membayangkan seberapa cepat tetrasi menjadi tidak terkendali: $latex 2 uparrowuparrow 3$, atau $latex 2^{2^2}$, adalah 16, $latex 2 uparrowuparrow 4$ hanya di atas 65,000, dan $latex 2 uparrowuparrow 5$ adalah angka dengan hampir 20,000 digit. Secara fisik mustahil untuk menuliskan semua digit $lateks 2 ke atas dan ke atas 6$ — sebuah tanggung jawab untuk hidup di alam semesta yang begitu kecil.

Dalam hasil penting mereka, Czerwiński dan rekan-rekannya membuktikan bahwa terdapat sistem penambahan ukuran vektor n dimana cara terbaik untuk menentukan keterjangkauan adalah dengan memetakan jalur yang melibatkan lebih dari transisi $latex 2 uparrowuparrow n$, yang menyiratkan batas bawah baru yang membuat batas bawah Lipton terlihat kerdil. Namun, meskipun tetrasi sangat membingungkan, hal ini masih belum menyelesaikan kompleksitas permasalahan yang ada.

Ke Quinquagintillion dan seterusnya 

Hanya beberapa bulan setelah batasan baru yang mengejutkan mengenai kompleksitas jangkauan VAS, Leroux dan Schmitz dorong kebawah batas atas yang mereka tetapkan tiga tahun sebelumnya, tetapi mereka tidak sampai pada tahap tetrasi. Sebaliknya, mereka membuktikan bahwa kompleksitas masalah keterjangkauan tidak bisa berkembang lebih cepat daripada keburukan matematis yang disebut fungsi Ackermann.

Untuk memahami fungsi tersebut, ambillah pola yang digunakan untuk mendefinisikan tetrasi sampai pada kesimpulan yang suram. Operasi selanjutnya dalam barisan, disebut pentatasi, mewakili tetrasi berulang; itu diikuti oleh operasi lain (hexation) untuk pentatasi berulang, dan seterusnya.

Fungsi Ackermann, dilambangkan dengan $latex A(n)$, adalah fungsi yang diperoleh ketika Anda menaiki satu tingkat tangga operasi ini dengan setiap perhentian pada garis bilangan: $latex A(1) = 1 + 1$, $latex A (2) = 2 × 2$, $lateks A(3) = 3^3$, $lateks A(4)=4 uparrowuparrow 4=4^{4^{4^4}}$, dan seterusnya. Jumlah digit dalam $latex A(4)$ sendiri merupakan angka yang sangat besar yang kira-kira sama dengan 1 quinquagintillion — itulah nama aneh dan jarang diperlukan untuk angka 1 diikuti dengan 153 angka nol. “Jangan khawatir tentang Ackermann dari 5,” saran Javier Esparza, seorang ilmuwan komputer di Universitas Teknik Munich.

Hasil yang diperoleh Leroux dan Schmitz meninggalkan kesenjangan yang besar antara batas bawah dan batas atas — kompleksitas masalah keterjangkauan VAS dapat terletak pada kedua ujung rentang atau di antara keduanya. Czerwiński tidak bermaksud membiarkan kesenjangan itu bertahan. “Kami terus mengerjakan ini karena jelas ini adalah hal terbesar yang pernah kami lakukan dalam hidup kami,” katanya.

Terobosan terakhir terjadi pada tahun 2021, ketika Czerwiński menjadi penasihat seorang mahasiswa sarjana tahun kedua bernama Łukasz Orlikowski. Dia menugaskan Orlikowski varian sederhana dari masalah tersebut untuk mempercepatnya, dan pekerjaan Orlikowski membantu mereka berdua mengembangkan teknik baru yang juga diterapkan pada masalah keterjangkauan secara umum. Itu memungkinkan mereka melakukannya menaikkan batas bawah secara substansial - sampai ke batas atas Ackermann milik Leroux dan Schmitz. Bekerja secara mandiri, Leroux memperoleh hasil yang setara sekitar waktu yang sama.

Terakhir, para peneliti telah menemukan kompleksitas sebenarnya dari masalah keterjangkauan. Batas bawah Czerwiński, Orlikowski, dan Leroux menunjukkan bahwa terdapat rangkaian sistem penjumlahan vektor yang semakin besar di mana jalur terpendek antara dua keadaan bertambah sebanding dengan fungsi Ackermann. Batas atas Leroux dan Schmitz menunjukkan bahwa masalah keterjangkauan tidak bisa menjadi lebih rumit dari itu — tidak ada penghiburan bagi siapa pun yang mengharapkan prosedur praktis yang sempurna untuk menyelesaikannya. Ini adalah ilustrasi yang mencolok tentang betapa rumitnya masalah komputasi yang tampaknya sederhana.

Tidak Pernah Selesai

Para peneliti terus mempelajari masalah keterjangkauan VAS setelah menentukan kompleksitas pastinya, karena masih banyak varian pertanyaan yang belum terjawab. Batas atas dan bawah Ackermann, misalnya, tidak membedakan cara peningkatan yang berbeda n, seperti meningkatkan dimensi vektor atau meningkatkan jumlah transisi yang diperbolehkan.

Baru-baru ini, Czerwiński dan rekan-rekannya melakukannya membuat kemajuan memisahkan efek-efek berbeda ini dengan mempelajari seberapa cepat kompleksitas dapat meningkat dalam varian sistem penjumlahan vektor dengan dimensi tetap. Namun masih banyak yang harus dilakukan – bahkan dalam tiga dimensi, dimana sistem penjumlahan vektor mudah divisualisasikan, kompleksitas masalah keterjangkauan masih belum diketahui.

“Di satu sisi, ini memalukan bagi kami,” kata Mazowiecki.

Para peneliti berharap bahwa pemahaman yang lebih baik tentang kasus-kasus yang relatif sederhana akan membantu mereka mengembangkan alat baru untuk mempelajari model komputasi lain yang lebih rumit daripada sistem penjumlahan vektor. Saat ini, kita hampir tidak mengetahui apa pun tentang model yang lebih rumit ini.

“Saya memandang ini sebagai bagian dari pencarian yang sangat mendasar untuk memahami kemampuan komputasi,” kata Zetzsche.

Quanta sedang melakukan serangkaian survei untuk melayani audiens kami dengan lebih baik. Ambil milik kami survei pembaca ilmu komputer dan anda akan diikut sertakan untuk menang secara gratis Quanta dagangan.