MEMILIH BILANGAN YANG JUMLAHNYA PAS, HAMPIR SECEPAT MEMBACANYA

Inilah teka-teki yang bisa dirumuskan siapa saja. Anda punya daftar bilangan bulat — misalnya 3, 9, 14, 20 — dan sebuah target, misalnya 23. Bisakah Anda memilih sebagian di antaranya agar jumlahnya tepat sama dengan target? (Di sini, bisa: 3 + 20 atau 9 + 14.) Inilah Subset Sum (jumlah subhimpunan), salah satu soal paling mendasar dalam ilmu komputer. Makalah ini menyebutnya sebagai soal NP-lengkap yang mendasar, keluarga soal yang dikenal sulit dipecahkan secara eksak.

Namun, ada celahnya. Jika bilangan-bilangannya tidak terlalu besar, algoritma yang cerdik berjalan dalam waktu yang bergantung pada besarnya. Metode klasik, karya Bellman pada 1957, membutuhkan waktu sebanding dengan banyaknya bilangan n dikali target t. Sejak itu, algoritmanya terus membaik:

• Pisinger (1999): sebanding dengan n × N, dengan N bilangan terbesar;
• Bringmann (2017): kira-kira n + t;
• beberapa tim (2021–2024): kira-kira n + N^(5/3), lalu n + N^(3/2).

Cawan sucinya adalah waktu kira-kira n + N — tidak jauh lebih lama daripada membaca masukannya. Para peneliti di bidang ini menyebutnya “soal terbuka paling krusial” dalam alur penelitian ini.

Tinggal selangkah dari tujuan

Lin Chen, Yuchen Mao, dan Guochuan Zhang dari Universitas Zhejiang di Tiongkok menyajikan algoritma yang berjalan dalam waktu n + N^(1+ε), dengan ε bisa berupa bilangan positif kecil apa pun yang ditetapkan sebelumnya — 0,1, 0,01, 0,001. Algoritma ini deterministik, menerima bilangan negatif dan nilai berulang, serta disertai bukti matematis. Para penulis menyebut waktu ini hampir optimal.

Hasilnya meluas ke vektor: memilih item agar beberapa jumlah sekaligus mencapai targetnya masing-masing, dengan waktu N^(d+ε) untuk d koordinat. Hal ini pada gilirannya menjawab sebagian pertanyaan yang diajukan beberapa kelompok tentang pemrograman bilangan bulat — mencari solusi bilangan bulat untuk sistem persamaan yang variabelnya terbatas. Dua konsekuensinya diuraikan secara eksplisit: membagi sebuah himpunan bilangan menjadi dua bagian yang sama, dan membagi pekerjaan antara dua mesin identik serata mungkin.

Mengangkat bilangan ke dimensi yang lebih tinggi

Gagasan kuncinya bersifat geometris. Sudah diketahui bahwa soal ini mudah jika bilangan-bilangannya rapat dan targetnya terletak jauh di dalam rentang jumlah yang mungkin. Pengamatan para penulis: himpunan bilangan yang jarang bisa tampak rapat jika dilihat dalam dimensi yang lebih tinggi.

Contoh mereka adalah himpunan {11, 12, 22, 24}. Tuliskan 11 dan 22 sebagai satu langkah dan dua langkah di sepanjang sumbu pertama, serta 12 dan 24 sebagai satu langkah dan dua langkah di sepanjang sumbu kedua. Jumlah-jumlah yang mungkin lalu mengisi setiap titik sebuah persegi kecil 4 kali 4. Namun, pipihkan kembali persegi itu ke sebuah garis — dengan menghitung 11x + 12y — maka jumlah-jumlah itu membentuk tujuh gugus terpisah dengan celah di antaranya, tersebar antara 0 dan 69. Celah-celah itu hanyalah ilusi dari proyeksi; dalam dua dimensi, strukturnya sederhana.

Algoritma ini membangun koordinat berdimensi lebih tinggi semacam itu untuk masukan apa pun, dengan memakai hasil-hasil dari kombinatorika aditif. Di dalam wilayah yang “terisi”, jawabannya didapat cuma-cuma. Hanya zona tipis di dekat tepi yang butuh kerja sungguhan, yang dipecah algoritma menjadi soal-soal lebih kecil dan diselesaikan secara rekursif. Setiap putaran memangkas zona itu secara tajam, dan hanya sejumlah konstan dimensi baru yang pernah ditambahkan.

Bagaimana bukti ini dibangun

Makalah ini dibuka dengan “penafian AI”. Para penulis merancang sendiri jalur utama pembuktiannya, berdasarkan karya terbaru mereka sendiri tentang versi soal yang rapat dan multidimensi. Mereka lalu memakai model AI, GPT Astra Ultra, untuk mengubah gagasan-gagasan itu menjadi bukti matematis yang lengkap. Model itu tersendat pada beberapa lema, yang kemudian diselesaikan dengan gagasan dari para penulis; sebuah catatan riset publik mendokumentasikan percakapannya. Setelah algoritma acak dasarnya selesai, model itu memperluasnya ke versi deterministik dan multidimensi “tanpa bimbingan apa pun dari para penulis”. Model itu juga menyusun draf makalahnya dan, tulis para penulis, memverifikasi hasil-hasil utamanya dengan bukti dalam asisten pembuktian Lean 4. Para penulis memikul tanggung jawab penuh atas isinya.

Belum sepenuhnya garis akhir

Eksponennya 1 + ε, bukan tepat 1, dan konstanta tersembunyinya membesar seiring mengecilnya ε; ketergantungan pada jumlah dimensi belum dioptimalkan. Para penulis sendiri menggambarkan algoritma itu “cukup rumit”. Makalah ini bersifat teoretis: tidak melaporkan implementasi maupun uji kinerja.