جدوں 1 دی قیمت 0 توں ودھ ہووے، کمپریشن اوکھا ہو جاندا اے

کسے لکھت نوں سُنگیڑ کے سانبھن جاں بھیجن لئی، ہر نشان (symbol) نوں 0 تے 1 توں بنیا اک لفظ دیو، عام نشاناں لئی چھوٹا تے ورلے نشاناں لئی لما۔ لفظاں نوں اک پری فکس کوڈ (prefix code) بناؤنا چاہیدا اے: کوئی لفظ کسے دوجے لفظ دا مُڈھ نہیں ہو سکدا۔ {0, 10, 11} چلدا اے؛ {0, 01, 11} نہیں چلدا، کیونکہ 01 دا مُڈھ 0 اے۔ پری فکس کوڈ نال، بِٹاں دی اک لمی لڑی نوں بنا کسے وکھریویں (separator) دے واپس لفظاں وچ کٹیا جا سکدا اے۔

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

جدوں حرفاں دی قیمت ہووے

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

ایس روپ دی اک لمی تاریخ اے۔ آر. ایم. کارپ (R. M. Karp) نے 1961 وچ ایہنوں اک انٹیجر پروگرامنگ (integer programming) مسئلے وانگ لکھیا۔ بعد دے کم نے پوری گنتی (integer) والیاں قیمتاں دی کسے وی پکی جوڑی لئی ٹھیک تے تیز (efficient) الگورتھم لبھے، تے اک تخمینی سکیم (approximation scheme) وی جو جِنا چاہو بہترین حل (optimum) دے نیڑے اپڑ جاندی اے۔ پر جدوں قیمتاں آپ ان پٹ (input) دا حصہ ہون، کسے نوں نہیں پتہ سی کہ مسئلہ کِنا اوکھا اے۔ 2021 تیکر وی، ایہہ کھلے مسئلیاں وچ گنیا جاندا سی۔

جواب: NP-complete

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

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

کوڈنگ دے اک رُکھ وچ لُکی بجھارت

ثبوت اک جانے پچھانے اوکھے مسئلے توں شروع ہوندا اے: اک ورقے اُتے بنا کسے لکیر دے اک دوجی نوں کٹے (without crossings) واہے گئے نیٹ ورک وچ، کیہ تسیں k نقطے چُن سکدے او جیہناں وچوں کوئی دو آپس وچ جُڑے نہ ہون؟ فیر ایہہ کوڈنگ دا اک مسئلہ بناؤندا اے جیہدا سبھ توں سستا کوڈ اوس سوال دا جواب دیندا اے۔

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

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

اوکھیائی کتھے لُکی اے

اک دوجا نتیجہ مسئلے نوں عام کوڈنگ دے اندر لبھدا اے۔ ہفمین دا نسخہ سبھ توں گھٹ اوسط لمبائی چھیتی لبھ لیندا اے۔ پر اوہ لمبائی اپڑن والے سارے کوڈاں وچوں، تکرار دے حساب نال تولے ہوئے سبھ توں گھٹ 1 والا کوڈ چُننا وی NP-complete اے۔

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

اک AI نال لبھیا ثبوت

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