Misteri Tak Terpecahkan dalam Dunia Pengkodean Jaringan

Ketidakmungkinan Pemecahan Tiga Masalah Utama dalam Pengkodean Jaringan dan Teori Informasi 

 Nirmala Febriyanti Putri

Makalah ini membahas penyelesaian tiga masalah terbuka yang telah lama ada, yaitu keputusan (decidability) algoritmik dari pengkodean jaringan (network coding), keputusan dari ketidaksamaan informasi bersyarat (conditional information inequalities), dan keputusan dari implikasi ketergantungan bersyarat (conditional independence implication) di antara variabel acak. Diketahui bahwa ketiga masalah ini tidak dapat dipecahkan (undecidable). Bukti yang diberikan menggunakan konstruksi yang terinspirasi dari argumen Herrmann tentang dependensi database multivaluasi yang tersemat, serta sebuah jaringan yang dipelajari oleh Dougherty, Freiling, dan Zeger, ditambah dengan konstruksi baru untuk merepresentasikan automorfisme grup di atas jaringan.

Kesimpulan dari makalah ini adalah bahwa ketiga masalah terbuka tersebut -- keputusan algoritmik dari pengkodean jaringan, ketidaksamaan informasi bersyarat, dan implikasi ketergantungan bersyarat -- terbukti tidak dapat dipecahkan. Hal ini menggarisbawahi kompleksitas dan batasan dari masalah-masalah ini dalam konteks teori informasi dan pengkodean jaringan.

Sumber