KETIKA ANGKA 1 LEBIH MAHAL DARIPADA 0, KOMPRESI MENJADI SULIT

Untuk menyimpan atau mengirim sebuah teks secara ringkas, berikan setiap simbol sebuah kata yang tersusun dari 0 dan 1, pendek untuk simbol yang sering muncul dan lebih panjang untuk simbol yang jarang. Kata-kata itu harus membentuk sebuah kode prefiks (prefix code): tidak ada kata yang boleh menjadi awal dari kata lain. {0, 10, 11} memenuhi syarat; {0, 01, 11} tidak, karena 01 diawali oleh 0. Dengan kode prefiks, deretan bit yang panjang dapat dipotong kembali menjadi kata-kata tanpa pemisah apa pun.

Kode terbaik semacam itu — yang panjang rata-ratanya paling kecil — ditemukan pada 1952 oleh D. A. Huffman, dengan resep serakah (greedy) sederhana yang berjalan cepat.

Ketika huruf punya harga

Resep Huffman mengandaikan bahwa 0 dan 1 berbiaya sama. Andaikan tidak: angka 1 membutuhkan waktu lebih lama untuk dikirim, atau ruang lebih besar untuk disimpan. Kini biaya setiap kata adalah jumlah biaya huruf-hurufnya, dan susunan sebuah kata sama pentingnya dengan panjangnya. Dengan biaya 1 dan 3, misalnya, 00 dan 01 sama panjang tetapi berbiaya 2 dan 4.

Varian ini punya sejarah panjang. R. M. Karp merumuskannya sebagai masalah pemrograman bilangan bulat pada 1961. Penelitian-penelitian berikutnya menemukan algoritme yang eksak dan efisien untuk setiap pasangan tetap biaya bilangan bulat, serta sebuah skema aproksimasi yang dapat mendekati optimum sedekat yang diinginkan. Tetapi ketika biaya-biaya itu sendiri menjadi bagian dari masukan, tidak ada yang tahu seberapa sulit masalahnya. Hingga 2021, masalah ini masih tercantum sebagai masalah terbuka.

Jawabannya: NP-lengkap

L. Sunil Chandran, dari Indian Institute of Science di Bengaluru, dan Rishikesh Gajjala, dari Pramaana Labs, kini membuktikan bahwa menentukan apakah ada kode dengan biaya paling banyak K adalah masalah NP-lengkap (NP-complete) — bahkan ketika kedua biaya itu adalah bilangan bulat berurutan, M dan M + 1. Para ilmuwan komputer menyebut sebuah masalah NP-lengkap jika masalah itu sama sulitnya dengan seluruh keluarga masalah klasik: metode umum yang cepat untuk salah satunya akan memberikan metode cepat untuk semuanya, dan belum ada yang diketahui. Karena itu, mencari kode termurah adalah masalah NP-sulit (NP-hard).

Hal ini tidak bertentangan dengan algoritme-algoritme cepat untuk biaya tetap. Dalam bukti ini, M membesar seiring masukan; untuk setiap pasangan biaya yang ditetapkan sebelumnya, algoritme-algoritme itu tetap berlaku.

Teka-teki yang tersembunyi dalam pohon kode

Bukti ini berangkat dari sebuah masalah sulit yang sudah dikenal: dalam sebuah jaringan yang digambar di selembar kertas tanpa persilangan, dapatkah kita memilih k titik yang tidak ada dua pun di antaranya yang terhubung? Bukti ini lalu menyusun sebuah masalah pengodean yang kode termurahnya menjawab pertanyaan itu.

1. Setiap kode prefiks adalah sebuah pohon: 0 ke kiri, 1 ke kanan. Sebuah kata dengan kedalaman d yang memuat z angka 1 berbiaya M × d + z jika huruf-hurufnya berbiaya M dan M + 1. Kedalaman menentukan bagian besar dari biaya, dan banyaknya angka 1 bagian kecilnya.
2. Para penulis merancang sebuah masalah perantara baru: tetapkan berapa banyak daun yang dimiliki pohon di setiap kedalaman, lalu beri skor pada posisi daun-daunnya. Mereka menunjukkan bahwa sebuah pohon yang murah, sambil tumbuh tingkat demi tingkat, harus menjalankan sebuah program kecil yang memeriksa titik-titik yang dipilih satu per satu, menyalin setiap pilihan, dan menguji setiap tautan. Setiap jalan pintas berbiaya paling sedikit satu satuan lebih banyak; setiap titik yang dipilih menghemat tepat satu satuan.
3. Terakhir, frekuensi-frekuensi diatur sedemikian rupa sehingga setiap simbol dipaksa berada di kedalaman yang tepat, dan skornya menjadi biaya pengodean ditambah suatu jumlah tetap.

Sebuah contoh kecil dari makalah ini menunjukkan betapa halusnya perhitungan biaya itu. Tiga simbol memiliki frekuensi 20, 12, dan 9, dan biaya hurufnya 83 dan 84. Kode (0, 10, 11) berbiaya 5.176. Kode (1, 00, 01) berbiaya 5.175: memberikan huruf yang mahal kepada simbol yang paling sering muncul justru menang, karena dua kata lainnya lalu memuat lebih sedikit angka 1.

Di mana kesulitannya bersembunyi

Hasil kedua menemukan sumber masalahnya di dalam pengodean biasa. Resep Huffman menemukan panjang rata-rata terpendek dengan cepat. Tetapi di antara semua kode yang mencapai panjang itu, memilih kode dengan angka 1 paling sedikit, dibobot menurut frekuensi, juga merupakan masalah NP-lengkap.

Beberapa pertanyaan masih tersisa: apakah masalah ini tetap sulit ketika semua bilangannya kecil (yang disebut NP-sulit dalam arti kuat, strong NP-hardness), dan apakah sebuah skema cepat dapat mendekati optimum dengan presisi berapa pun, dengan waktu komputasi yang juga tumbuh secara wajar seiring presisi itu.

Bukti yang ditemukan dengan AI

Makalah ini menyatakan bagaimana bukti itu diperoleh. Para penulis mula-mula meminta Codex dari OpenAI untuk membuat bukti kesulitan bagi sebuah masalah yang lebih umum, lalu memintanya memperluas bukti itu ke kode nonbiner dan akhirnya ke kode biner. Codex berkontribusi pada strategi reduksinya dan pengembangan matematisnya; Codex juga membantu penulisan draf, pemeriksaan argumen, dan penyusunan contoh. Para penulis mengarahkan pekerjaan itu, meminta koreksi dan penyederhanaan, menulis ulang pemaparannya secara substansial, dan bertanggung jawab atas pernyataan dan bukti akhirnya. Seperti setiap pracetak, makalah ini belum ditelaah sejawat.