حين يكلّف الرقم 1 أكثر من 0، يصبح الضغط صعبًا

لتخزين نص أو إرساله بإيجاز، امنح كل رمز كلمةً مؤلفة من 0 و1، قصيرة للرموز الشائعة وأطول للنادرة. ويجب أن تشكّل الكلمات شفرة بادئة (prefix code): لا يجوز أن تكون أي كلمة بدايةً لكلمة أخرى. فالمجموعة {0, 10, 11} تصلح؛ أما {0, 01, 11} فلا، لأن 0 هو بداية 01. ومع شفرة بادئة، يمكن تقطيع سلسلة طويلة من البتّات إلى كلماتها من جديد دون أي فاصل.

وأفضل شفرة من هذا النوع — أي تلك ذات أصغر طول متوسط — اكتُشفت عام 1952 على يد هافمان (D. A. Huffman)، بوصفة جشعة (greedy) بسيطة تعمل بسرعة.

حين يكون للحروف ثمن

تفترض وصفة هافمان أن 0 و1 يكلّفان القدر نفسه. لنفترض أن الأمر ليس كذلك: فالـ1 يستغرق وقتًا أطول للإرسال، أو حيزًا أكبر للتخزين. عندئذ تكلّف كل كلمة مجموع حروفها، ويصبح تركيب الكلمة مهمًا بقدر طولها. فمع التكلفتين 1 و3 مثلًا، تتساوى 00 و01 في الطول لكن كلفتيهما 2 و4.

ولهذا الشكل من المسألة تاريخ طويل. ففي عام 1961، صيغت في عمل ر. م. كارب (R. M. Karp) مسألةَ برمجة بالأعداد الصحيحة (integer programming). ووجدت أعمال لاحقة خوارزميات دقيقة وفعّالة لأي زوج ثابت من التكاليف الصحيحة، ومخطط تقريب يقترب من الحل الأمثل بالقدر المرغوب. لكن حين تكون التكاليف نفسها جزءًا من المدخلات، لم يكن أحد يعرف مدى صعوبة المسألة. وحتى عام 2021، كانت لا تزال مدرجة بين المسائل المفتوحة.

الجواب: NP-كاملة

ويقدّم الآن بحث جديد، من إعداد ل. سونيل تشاندران (L. Sunil Chandran)، من المعهد الهندي للعلوم في بنغالورو، وريشيكيش غاجالا (Rishikesh Gajjala)، من مختبرات برامانا (Pramaana Labs)، إثباتًا أن تحديد ما إذا كانت توجد شفرة كلفتها K على الأكثر مسألة NP-كاملة (NP-complete) — حتى عندما تكون التكلفتان عددين صحيحين متتاليين، M وM + 1. ويصف علماء الحاسوب مسألةً بأنها NP-كاملة حين تكون صعبة بقدر عائلة كاملة من المسائل الكلاسيكية: فطريقة عامة سريعة لإحداها تعطي طريقة لها جميعًا، ولا تُعرف أي طريقة كهذه. ولذا فإن إيجاد أرخص شفرة مسألة NP-صعبة (NP-hard).

ولا تناقض في ذلك مع الخوارزميات السريعة الخاصة بالتكاليف الثابتة. ففي البرهان، تكبر M مع المدخلات؛ أما لأي زوج من التكاليف مثبّت مسبقًا، فتظل تلك الخوارزميات صالحة.

لغز مخبّأ في شجرة ترميز

ينطلق البرهان من مسألة صعبة معروفة: في شبكة مرسومة على ورقة دون تقاطعات، هل يمكن اختيار k نقطة لا ترتبط أي اثنتين منها؟ ثم يبني مسألة ترميز تجيب أرخصُ شفرة فيها عن هذا السؤال.

1. أي شفرة بادئة هي شجرة: 0 يذهب يسارًا، و1 يذهب يمينًا. والكلمة ذات العمق d التي تحوي z من الآحاد تكلّف M × d + z عندما تكون كلفة الحرفين M وM + 1. فالعمق يحدد الجزء الكبير من الكلفة، وعدد الآحاد الجزء الصغير.
2. يصمم البحث مسألة وسيطة جديدة: تثبيت عدد الأوراق التي تملكها الشجرة عند كل عمق، وإعطاء علامة لمواقع أوراقها. ويبيّن أن الشجرة الرخيصة يجب، وهي تنمو مستوى بعد مستوى، أن تنفّذ برنامجًا صغيرًا يفحص النقاط المختارة واحدة تلو الأخرى، وينسخ كل اختيار ويختبر كل رابط. وأي اختصار يكلّف وحدة واحدة إضافية على الأقل؛ وكل نقطة مختارة توفّر وحدة واحدة بالضبط.
3. وأخيرًا، تُضبط التكرارات بحيث يُجبَر كل رمز على العمق الصحيح، وتصبح العلامة هي كلفة الترميز مضافًا إليها مقدار ثابت.

ويُظهر مثال صغير من الورقة مدى دقة التكاليف. ثلاثة رموز تكراراتها 20 و12 و9، وكلفة الحرفين 83 و84. الشفرة (0, 10, 11) تكلّف 5,176. أما الشفرة (1, 00, 01) فتكلّف 5,175: فإعطاء الحرف الأغلى للرمز الأكثر تكرارًا هو الخيار الرابح، لأن الكلمتين الأخريين تحملان عندئذ عددًا أقل من الآحاد.

أين تختبئ الصعوبة

تحدد نتيجة ثانية موضع المشكلة داخل الترميز العادي. فوصفة هافمان تجد أقصر طول متوسط بسرعة. لكن من بين كل الشفرات التي تبلغ ذلك الطول، فإن اختيار الشفرة ذات أقل عدد من الآحاد، موزونًا بالتكرار، مسألة NP-كاملة هي الأخرى.

وتبقى أسئلة مطروحة: هل تظل المسألة صعبة عندما تكون كل الأعداد صغيرة (ما يُسمّى الصعوبة القوية من الصنف NP، أو strong NP-hardness)، وهل يمكن لمخطط سريع أن يقارب الحل الأمثل بأي دقة، بزمن تشغيل ينمو أيضًا على نحو معقول مع تلك الدقة.

برهان وُجد بمساعدة ذكاء اصطناعي

تذكر الورقة كيف جرى التوصل إليه. فقد طلب المؤلفان أولًا من Codex التابع لـOpenAI برهانًا على صعوبة مسألة أعم، ثم طلبا منه توسيعه إلى الشفرات غير الثنائية، وأخيرًا إلى الشفرات الثنائية. وأسهم Codex في استراتيجية الاختزال (reduction) وفي تطويرها الرياضي؛ كما ساعد في الصياغة والتحقق من الحجج وبناء الأمثلة. ووجّه المؤلفان العمل، وطلبا تصحيحات وتبسيطات، وأعادا كتابة العرض إلى حد كبير، ويتحمّلان المسؤولية عن صياغة النتائج النهائية وبراهينها. ومثل أي مسودة بحثية (preprint)، لم تخضع بعدُ لتحكيم الأقران.