جب 1 کی قیمت 0 سے زیادہ ہو، تو کمپریشن مشکل ہو جاتا ہے

کسی متن کو مختصر صورت میں محفوظ کرنے یا بھیجنے کے لیے، ہر علامت کو 0 اور 1 سے بنا ایک لفظ دیں: کثرت سے آنے والی علامتوں کے لیے چھوٹا اور کم آنے والی علامتوں کے لیے لمبا۔ ان الفاظ کو ایک سابقہ کوڈ (prefix code) بنانا چاہیے: کوئی لفظ کسی دوسرے لفظ کا آغاز نہیں ہو سکتا۔ {0, 10, 11} چلتا ہے؛ {0, 01, 11} نہیں چلتا، کیونکہ 01 کا آغاز 0 سے ہوتا ہے۔ سابقہ کوڈ کے ساتھ، بِٹس کی ایک لمبی لڑی کو کسی فاصل (separator) کے بغیر واپس الفاظ میں کاٹا جا سکتا ہے۔

ایسا بہترین کوڈ — جس کی اوسط لمبائی سب سے کم ہو — 1952 میں D. A. Huffman نے ڈھونڈا، ایک سادہ لالچی (greedy) نسخے کے ذریعے جو تیزی سے چلتا ہے۔

جب حروف کی قیمت ہو

Huffman کا نسخہ فرض کرتا ہے کہ 0 اور 1 کی قیمت برابر ہے۔ فرض کریں ایسا نہیں: 1 کو بھیجنے میں زیادہ وقت لگتا ہے، یا محفوظ کرنے میں زیادہ جگہ۔ اب ہر لفظ کی قیمت اس کے حروف کی قیمتوں کا مجموعہ ہے، اور لفظ کی ترکیب اتنی ہی اہم ہو جاتی ہے جتنی اس کی لمبائی۔ مثال کے طور پر قیمتیں 1 اور 3 ہوں، تو 00 اور 01 برابر لمبے ہیں لیکن ان کی قیمت 2 اور 4 ہے۔

اس صورت کی ایک لمبی تاریخ ہے۔ R. M. Karp نے 1961 میں اسے عددِ صحیح پروگرامنگ (integer programming) کے ایک مسئلے کے طور پر لکھا۔ بعد کے کام نے عددِ صحیح قیمتوں کے کسی بھی مقررہ جوڑے کے لیے قطعی اور مؤثر الگورتھم ڈھونڈے، اور ایک تخمینی طریقہ (approximation scheme) بھی جو بہترین حل کے جتنا چاہیں اتنا قریب پہنچ جاتا ہے۔ لیکن جب خود قیمتیں ان پٹ کا حصہ ہوں، تو کسی کو معلوم نہیں تھا کہ یہ مسئلہ کتنا مشکل ہے۔ 2021 تک بھی یہ کھلے مسائل کی فہرست میں شامل تھا۔

جواب: NP-مکمل

بنگلورو کے Indian Institute of Science کے L. Sunil Chandran اور Pramaana Labs کے Rishikesh Gajjala اب ثابت کرتے ہیں کہ یہ فیصلہ کرنا کہ آیا زیادہ سے زیادہ K قیمت کا کوئی کوڈ موجود ہے، NP-مکمل (NP-complete) ہے — اس وقت بھی جب دونوں قیمتیں متواتر اعدادِ صحیح ہوں، M اور M + 1۔ کمپیوٹر سائنس دان کسی مسئلے کو NP-مکمل اس وقت کہتے ہیں جب وہ کلاسیکی مسائل کے ایک پورے خاندان جتنا مشکل ہو: ان میں سے کسی ایک کا تیز عمومی طریقہ سب کے لیے تیز طریقہ دے دے گا، اور ایسا کوئی طریقہ معلوم نہیں۔ چنانچہ سب سے سستا کوڈ ڈھونڈنا NP-مشکل (NP-hard) ہے۔

مقررہ قیمتوں کے تیز الگورتھموں سے کوئی تضاد نہیں۔ ثبوت میں M ان پٹ کے ساتھ بڑھتا ہے؛ پہلے سے مقرر کیے گئے قیمتوں کے کسی بھی جوڑے کے لیے وہ الگورتھم اب بھی کارآمد ہیں۔

کوڈنگ کے درخت میں چھپی ایک پہیلی

ثبوت ایک معلوم مشکل مسئلے سے شروع ہوتا ہے: کاغذ پر بغیر کسی لکیر کو کاٹے کھینچے گئے ایک نیٹ ورک میں، کیا آپ ایسے k نقطے چن سکتے ہیں جن میں سے کوئی دو آپس میں جڑے ہوئے نہ ہوں؟ پھر یہ ایک ایسا کوڈنگ مسئلہ بناتا ہے جس کا سب سے سستا کوڈ اس سوال کا جواب دیتا ہے۔

ہر سابقہ کوڈ ایک درخت ہے: 0 بائیں جاتا ہے، 1 دائیں۔ جب حروف کی قیمت M اور M + 1 ہو، تو گہرائی d کا ایسا لفظ جس میں 1 کی تعداد z ہو، M × d + z قیمت رکھتا ہے۔ گہرائی قیمت کا بڑا حصہ طے کرتی ہے، اور 1 کی تعداد چھوٹا حصہ۔
مصنفین ایک نیا درمیانی مسئلہ وضع کرتے ہیں: طے کر دیں کہ درخت کی ہر گہرائی پر کتنے پتے (leaves) ہوں، اور اس بات کا اسکور (score) دیں کہ اس کے پتے کہاں واقع ہیں۔ وہ دکھاتے ہیں کہ ایک سستا درخت، جیسے جیسے سطح بہ سطح بڑھتا ہے، لازماً ایک چھوٹا پروگرام چلاتا ہے جو چنے گئے نقطوں کو ایک ایک کر کے جانچتا ہے، ہر انتخاب کی نقل بناتا ہے اور ہر ربط کو پرکھتا ہے۔ کوئی بھی شارٹ کٹ کم از کم ایک اکائی زیادہ مہنگا پڑتا ہے؛ ہر چنا گیا نقطہ ٹھیک ایک اکائی بچاتا ہے۔
آخر میں، تعدد (frequencies) اس طرح ترتیب دیے جاتے ہیں کہ ہر علامت درست گہرائی پر رہنے پر مجبور ہو، اور اسکور کوڈنگ کی قیمت جمع ایک مقررہ مقدار بن جائے۔

مقالے کی ایک چھوٹی مثال دکھاتی ہے کہ یہ قیمتیں کتنی باریک ہیں۔ تین علامتوں کے تعدد 20، 12 اور 9 ہیں، اور حروف کی قیمتیں 83 اور 84۔ کوڈ (0, 10, 11) کی قیمت 5,176 ہے۔ کوڈ (1, 00, 01) کی قیمت 5,175 ہے: مہنگا حرف سب سے زیادہ آنے والی علامت کو دینا فائدہ مند رہتا ہے، کیونکہ تب باقی دو الفاظ میں 1 کم آتے ہیں۔

مشکل کہاں چھپی ہے

ایک دوسرا نتیجہ اس مشکل کو عام کوڈنگ کے اندر ڈھونڈ نکالتا ہے۔ Huffman کا نسخہ سب سے کم اوسط لمبائی تیزی سے ڈھونڈ لیتا ہے۔ لیکن ان تمام کوڈز میں سے جو اس لمبائی تک پہنچتے ہیں، وہ کوڈ چننا جس میں تعدد کے لحاظ سے وزن دے کر، 1 سب سے کم ہوں، وہ بھی NP-مکمل ہے۔

سوالات باقی ہیں: کیا یہ مسئلہ اس وقت بھی مشکل رہتا ہے جب تمام اعداد چھوٹے ہوں (جسے مضبوط NP-مشکل پن یا strong NP-hardness کہا جاتا ہے)، اور کیا کوئی تیز طریقہ بہترین حل کا کسی بھی درستی تک تخمینہ لگا سکتا ہے، ایسے وقتِ عمل (running time) کے ساتھ جو اس درستی کے لحاظ سے بھی معقول حد تک ہی بڑھے۔

مصنوعی ذہانت کی مدد سے ملا ثبوت

مقالہ بتاتا ہے کہ یہ ثبوت کیسے حاصل ہوا۔ مصنفین نے پہلے OpenAI کے Codex سے ایک زیادہ عمومی مسئلے کی مشکل پن (hardness) کا ثبوت مانگا، پھر اس سے کہا کہ اسے غیر ثنائی (nonbinary) اور آخرکار ثنائی کوڈز تک پھیلائے۔ Codex نے تحویل (reduction) کی حکمتِ عملی اور اس کی ریاضیاتی تشکیل میں حصہ ڈالا؛ اس نے مسودہ لکھنے، دلائل جانچنے اور مثالیں بنانے میں بھی مدد کی۔ مصنفین نے کام کی رہنمائی کی، تصحیحات اور سادگیوں کی درخواست کی، بیان کو خاطر خواہ حد تک دوبارہ لکھا، اور حتمی بیانات اور ثبوتوں کی ذمہ داری لیتے ہیں۔ کسی بھی پری پرنٹ کی طرح، ابھی اس کا ہم مرتبہ جائزہ (peer review) نہیں ہوا۔