RUNTUHNYA PENGHALANG TAHUN 1962 DALAM ILMU KOMPUTER

Siklus Hamilton adalah perjalanan pulang-pergi melalui sebuah jaringan yang mengunjungi setiap titik tepat satu kali lalu kembali ke titik awal. Dalam jaringan berarah, setiap tautan adalah panah yang hanya bisa diikuti satu arah, seperti jalan satu arah. Versi berbobot dari masalah ini adalah masalah penjual keliling (travelling salesman) asimetris.

Menentukan apakah siklus seperti itu ada adalah masalah sulit yang ada di buku teks. Pada 1962, Richard Bellman dan, secara terpisah, Michael Held dan Richard Karp memberikan algoritma pemrograman dinamis yang menyelesaikannya dalam waktu sekitar 2ⁿ untuk jaringan dengan n titik (hingga faktor-faktor yang tumbuh secara polinomial saja). Selama lebih dari enam puluh tahun, tak seorang pun mampu berbuat jauh lebih baik secara mendasar pada jaringan berarah umum.

Sepupu tak berarahnya sudah lebih dulu runtuh

Untuk jaringan dengan tautan dua arah, Andreas Björklund menembus penghalang itu pada 2014 dengan algoritma acak yang berjalan dalam 1,657ⁿ, karya yang menghasilkan Hadiah Nerode EATCS–IPEC 2016 baginya, menurut makalah ini. Algoritma itu masih yang tercepat yang diketahui untuk jaringan tak berarah umum. Untuk jaringan berarah, kemajuan hanya datang pada kasus-kasus khusus — jaringan bipartit, jaringan dengan sedikit tautan per titik — atau dengan mengandalkan hipotesis yang belum terbukti, yaitu konjektur rank asimtotik Strassen.

Batas baru

Tomohiro Koana dari Universitas Tokyo dan Soh Kumabe dari perusahaan CyberAgent di Tokyo kini menyajikan algoritma acak yang memutuskan masalah berarah ini dalam waktu

O((375/196)ⁿ) = O(1,9133ⁿ)**.

Untuk jaringan berarah umum, ini adalah perbaikan pertama pada basis eksponensial sejak 1962.

Menghitung ganjil dan genap

Kesulitannya halus. Menghitung siklus modulo 2 — hanya mengetahui apakah jumlahnya ganjil atau genap — sudah dapat dilakukan di bawah 2ⁿ. Namun jumlah siklus yang genap dan tidak nol tampak persis sama dengan nol. Solusi klasiknya adalah memberi bobot acak pada tautan sehingga, pada bobot total tertentu, satu solusi menjadi unik (lema isolasi); tetapi metode cepat untuk menghitung paritas tidak dapat menangani bobot.

Resep para penulis, dalam bahasa sederhana:

Tebak satu panah dari siklus itu, lalu sebagai gantinya cari lintasan yang melewati setiap titik dari satu ujung panah itu ke ujung lainnya.
Hapus setiap panah secara acak dengan peluang 1/50.
Di setiap titik, buat tiga kelompok panah masuk, lalu salin setiap panah yang tersisa ke himpunan kelompok acak yang tidak kosong.
Jika rute keliling ada, maka dengan peluang setidaknya (49/50)ⁿ⁻¹ kita dapat memilih satu kelompok per titik sehingga jumlah lintasan yang sah adalah ganjil.
Beri setiap kelompok — bukan setiap panah — bobot acak. Sekarang trik isolasi berhasil, dan sekitar (50/49)ⁿ pengulangan sudah cukup.
Setiap pengulangan menghitung jumlah ganjil-atau-genap pada setiap bobot total dalam waktu (15/8)ⁿ, menggunakan jumlahan determinan matriks dari Björklund, Kaski, dan Koutis serta “linearisasi” acak yang juga dipakai oleh Arvind dan Guruswami.

Kalikan keduanya: (50/49)ⁿ × (15/8)ⁿ = (375/196)ⁿ ≈ 1,9133ⁿ.

Bukti yang dihasilkan mesin

Makalah ini diakhiri dengan pernyataan tentang AI generatif: ChatGPT 6 Astra menghasilkan bukti teorema utama dan membantu menyusun naskah. Para penulis menyediakan pernyataan proposisi-proposisi perantara, yang memberi tafsiran kombinatorial atas solusi asli model tersebut, lalu memeriksa dan merevisi semuanya serta memikul tanggung jawab penuh.

Hasil ini bersifat teoretis — tidak ada program yang dijalankan — dan algoritmanya bersifat acak, dengan kemungkinan kecil untuk keliru ke arah mana pun. Antara 1,9133 untuk jalan satu arah dan 1,657 untuk jalan dua arah, masih terbuka celah yang lebar.