MENCAMPUR PESAN MENGALAHKAN MERUTEKANNYA, SETELAH 22 TAHUN DIRAGUKAN

Bayangkan sebuah jaringan kabel tempat beberapa pengirim masing-masing ingin menjangkau penerimanya sendiri. Pendekatan klasiknya adalah perutean (routing): setiap pesan bepergian seperti paket melalui satu jalur atau lebih, dan lalu lintas bahkan dapat dibagi ke banyak jalur dalam proporsi berapa pun. Pengodean jaringan (network coding) menambahkan satu kebebasan lagi: simpul-simpul perantara boleh menggabungkan pesan yang mereka terima — misalnya dengan menjumlahkannya — alih-alih sekadar meneruskannya.

Pertanyaannya, apakah kebebasan itu pernah membuat lebih banyak data bisa lewat. Makalah ini berfokus pada jaringan tak berarah, tempat sebuah kabel dapat membawa data ke arah mana pun, tetapi kedua arah berbagi satu kapasitas yang sama.

Konjektur yang terkonfirmasi kasus demi kasus

Pada 2004, Li dan Li mengajukan konjektur bahwa dalam situasi ini pengodean tidak memberi keunggulan apa pun dibanding perutean fraksional; Harvey, Kleinberg, dan Rasala Lehman merumuskan konjektur yang sama secara terpisah. Selama dua dekade berikutnya, konjektur itu dikonfirmasi untuk satu kelas jaringan demi kelas lainnya — dua sesi, jaringan planar tertentu, jaringan dengan paling banyak enam simpul pengodean, dan lain-lain — tetapi tak pernah dituntaskan secara umum. Sejumlah hasil lain dalam teori kompleksitas, seperti batas bawah untuk pengurutan bilangan bulat di memori eksternal dan untuk sirkuit perkalian, bahkan sudah dibuktikan dengan mengasumsikan konjektur itu benar.

Teori yang sudah ada membatasi taruhannya: pengodean paling banyak bisa mengungguli perutean dengan faktor logaritmik. Dan hasil tahun 2017 dari Braverman, Garg, dan Schvartzman menunjukkan bahwa satu jaringan saja yang memiliki keunggulan pengodean secara tegas dapat diperbesar menjadi selisih yang jauh lebih besar. Semuanya bermuara pada menemukan satu contoh yang berhingga.

Menjumlahkan sudah cukup

Lampiran makalah memberikan perangkat dasarnya, yang menunjukkan mengapa pencampuran bisa membantu. Letakkan beberapa sumber di sekitar simpul pusat v, penerima mereka di sekitar simpul pusat lain w, lalu hubungkan v dan w dengan satu kabel. Setiap sumber juga punya jalur samping kecil menuju penerima-penerima lainnya. Dalam tiga putaran, kabel tengah membawa jumlah semua pesan; setiap penerima mendapat jumlah itu ditambah pesan-pesan lain dari jalur samping, lalu memulihkan pesannya sendiri dengan pengurangan. Tanpa kabel tengah, setiap sumber berjarak lima lompatan dari penerimanya.

Perangkat itu, dari karya terdahulu Haeupler, Wajc, dan Zuzic, membuat pengodean lebih cepat, tetapi dengan sendirinya belum mampu membawa lebih banyak: sebuah jalur panjang tetap bisa menjalankan aliran bersambung (pipeline) berlaju tinggi.

Sirkuit yang diubah menjadi jaringan

Xindan Zhang dan Baochun Li dari Universitas Toronto, serta Zongpeng Li dari Universitas Tsinghua, menemukan langkah yang hilang. Mereka mengubah sebuah kode pendek menjadi komputasi reversibel — sirkuit penjumlahan bilangan bulat yang dapat dibalik, yang menghitung, menyalin hasilnya, lalu membatalkan kerja antaranya. Kemudian mereka membangun jaringan baru yang kabel-kabel fisiknya adalah kabel-kabel sirkuit itu, dan memberi setiap register komputasi, termasuk register coretan, permintaan pengirim–penerimanya sendiri.

Perhitungan “waktu” yang cermat di sepanjang kabel menyelesaikan sisanya. Jika dijumlahkan atas semua kabel, panjangnya persis sama dengan jarak minimum yang harus ditempuh oleh semua permintaan. Namun permintaan yang ditetapkan tidak dapat menghindari gerbang-gerbang tertentu yang memakan dua satuan tambahan. Jadi perutean pasti tertinggal dari laju penuh, sementara kode memakai setiap kabel tepat satu kali dan, jika dijalankan bersambung atas banyak blok, mendekati laju satu.

Apa yang terbukti

• Sebuah jaringan terhubung yang berhingga, dengan setiap simpul terhubung ke paling banyak tiga simpul lain dan kapasitas satu di setiap kabel, tempat sebuah kode linear biner sederhana mengalahkan perutean fraksional terbaik yang mungkin. Konjektur tahun 2004 itu salah.
• Konstruksi bilangan bulat yang sama berlaku sekaligus atas setiap medan berhingga dan setiap grup abelian berhingga yang tak trivial.
• Dengan menggabungkan salinan berulang kali, para penulis membangun keluarga jaringan tak hingga tempat pengodean mendekati laju penuh sementara perutean turun seperti pangkat dari 1/log n — sebuah keunggulan polilogaritmik.

Makalah ini tidak menyebutkan jumlah simpul dalam contoh penyangkalnya. Blok penyusunnya saja sudah berupa kode yang berlangsung 13.122 putaran.

Diperiksa oleh mesin

Contoh penyangkal yang berhingga maupun teorema keluarga jaringan itu diformalkan dalam asisten pembuktian Lean. Menurut para penulis, audit atas 2.472 deklarasi dan 1.755 teorema menunjukkan bahwa pembuktian hanya memakai tiga aksioma standar Lean, tanpa pembuktian yang belum lengkap; pemeriksaan ulang independen di lingkungan baru juga berhasil, meskipun dengan inti (kernel) Lean yang sama.

Yang masih terbuka

Para penulis mendaftar tiga pertanyaan: besar keunggulan yang sebenarnya pada contoh berhingga mereka, apakah batas atas logaritmik yang diketahui benar-benar tercapai, dan apakah ada contoh penyangkal yang kecil. Kalimat terakhir mereka merangkum keadaannya: “Ternyata pengodean memang membantu dalam jaringan tak berarah; seberapa besar bantuannya masih harus dilihat.”

Penggunaan AI dinyatakan. Sebuah catatan kaki menyebutkan bahwa GPT-6 Astra dari OpenAI membantu mengembangkan pembuktian dan kode Lean.