BİR 1, BİR 0'DAN PAHALIYA GELİNCE SIKIŞTIRMA ZORLAŞIYOR

Bir metni kompakt biçimde saklamak ya da göndermek için her simgeye 0 ve 1’lerden oluşan bir kelime verin: sık geçen simgelere kısa, nadir olanlara daha uzun kelimeler. Kelimeler bir önek kodu oluşturmalıdır: hiçbir kelime bir başkasının başlangıcı olamaz. {0, 10, 11} işe yarar; {0, 01, 11} yaramaz, çünkü 01, 0 ile başlar. Bir önek koduyla, uzun bir bit dizisi hiçbir ayırıcı olmadan yeniden kelimelerine bölünebilir.

Bu türden en iyi kod — ortalama uzunluğu en küçük olan — 1952’de D. A. Huffman tarafından, hızlı çalışan basit bir açgözlü tarifle bulundu.

Harflerin bir fiyatı olunca

Huffman’ın tarifi, bir 0 ile bir 1’in aynı maliyete sahip olduğunu varsayar. Öyle olmadığını düşünelim: 1’in iletilmesi daha uzun sürüyor ya da saklanması daha fazla yer kaplıyor. Artık her kelimenin maliyeti, harflerinin maliyetlerinin toplamıdır ve bir kelimenin bileşimi en az uzunluğu kadar önemlidir. Örneğin maliyetler 1 ve 3 olduğunda, 00 ve 01 eşit uzunluktadır ama maliyetleri 2 ve 4’tür.

Bu varyantın uzun bir geçmişi var. R. M. Karp onu 1961’de bir tamsayılı programlama problemi olarak yazdı. Sonraki çalışmalar, tamsayı maliyetlerden oluşan herhangi bir sabit çift için kesin ve verimli algoritmalar ile optimuma istenildiği kadar yaklaşan bir yaklaşım şeması buldu. Ancak maliyetlerin kendisi girdinin bir parçası olduğunda, problemin ne kadar zor olduğunu kimse bilmiyordu. 2021 gibi yakın bir tarihte bile hâlâ açık bir problem olarak listeleniyordu.

Cevap: NP-tam

Bengaluru’daki Hindistan Bilim Enstitüsü’nden L. Sunil Chandran ve Pramaana Labs’ten Rishikesh Gajjala, maliyeti en fazla K olan bir kodun var olup olmadığına karar vermenin NP-tam olduğunu kanıtlıyor — iki maliyet ardışık tamsayılar, M ve M + 1 olsa bile. Bilgisayar bilimciler, bir problem bütün bir klasik problemler ailesi kadar zor olduğunda ona NP-tam der: biri için hızlı bir genel yöntem, hepsi için bir yöntem verirdi ve böyle bir yöntem bilinmiyor. Dolayısıyla en ucuz kodu bulmak NP-zor bir problemdir.

Sabit maliyetler için var olan hızlı algoritmalarla bir çelişki yok. Kanıtta M girdiyle birlikte büyüyor; önceden sabitlenmiş herhangi bir maliyet çifti için bu algoritmalar hâlâ geçerli.

Bir kodlama ağacında gizlenmiş bir bulmaca

Kanıt, bilinen zor bir problemden yola çıkıyor: bir kâğıda kesişmeler olmadan çizilmiş bir ağda, hiçbir ikisi birbirine bağlı olmayan k nokta seçebilir misiniz? Ardından, en ucuz kodu bu soruyu cevaplayan bir kodlama problemi kuruyor.

Her önek kodu bir ağaçtır: 0 sola, 1 sağa gider. Harflerin maliyeti M ve M + 1 olduğunda, d derinliğinde ve z tane 1 içeren bir kelimenin maliyeti M × d + z’dir. Derinlik maliyetin büyük kısmını, 1’lerin sayısı ise küçük kısmını belirler.
Yazarlar yeni bir ara problem tasarlıyor: ağacın her derinlikte kaç yaprağı olduğunu sabitleyin ve yapraklarının nerede durduğunu puanlayın. Ucuz bir ağacın, seviye seviye büyürken, seçilen noktaları tek tek kontrol eden, her seçimi kopyalayan ve her bağlantıyı test eden küçük bir program çalıştırması gerektiğini gösteriyorlar. Her kestirme yol en az bir birim daha pahalıya mal oluyor; seçilen her nokta tam olarak bir birim tasarruf sağlıyor.
Son olarak frekanslar, her simge doğru derinliğe zorlanacak şekilde ayarlanıyor ve puan, kodlama maliyeti artı sabit bir miktara dönüşüyor.

Makaledeki küçük bir örnek, maliyetlerin ne kadar ince işlediğini gösteriyor. Üç simgenin frekansları 20, 12 ve 9; harflerin maliyetleri 83 ve 84. (0, 10, 11) kodunun maliyeti 5.176. (1, 00, 01) kodunun maliyeti ise 5.175: pahalı harfi en sık geçen simgeye vermek kazandırıyor, çünkü diğer iki kelime bu durumda daha az 1 taşıyor.

Zorluk nerede saklanıyor

İkinci bir sonuç, sorunun kaynağını sıradan kodlamanın içinde buluyor. Huffman’ın tarifi en kısa ortalama uzunluğu hızla bulur. Ama bu uzunluğa ulaşan tüm kodlar arasından, frekansa göre ağırlıklandırılmış en az sayıda 1 içereni seçmek de NP-tam.

Açık sorular kalıyor: tüm sayılar küçük olduğunda problemin zor kalıp kalmadığı (güçlü NP-zorluk denen özellik) ve hızlı bir şemanın, çalışma süresi o hassasiyetle birlikte de makul ölçüde büyüyerek, optimuma istenen her hassasiyetle yaklaşıp yaklaşamayacağı.

Bir yapay zekâyla bulunan kanıt

Makale, nasıl elde edildiğini açıkça belirtiyor. Yazarlar önce OpenAI’ın Codex’inden daha genel bir problem için bir zorluk kanıtı istedi, ardından onu ikili olmayan kodlara ve en sonunda ikili kodlara genişletmesini istedi. Codex, indirgemenin stratejisine ve matematiksel gelişimine katkıda bulundu; ayrıca taslağın yazımına, argümanların kontrolüne ve örneklerin oluşturulmasına yardım etti. Yazarlar çalışmayı yönlendirdi, düzeltmeler ve sadeleştirmeler istedi, anlatımı büyük ölçüde yeniden yazdı ve nihai önermelerin ve kanıtların sorumluluğunu üstleniyor. Her ön baskı gibi, henüz hakem değerlendirmesinden geçmedi.