مشکل مسائل کو حل کرنے کا بہترین طریقہ کیا ہے؟ کمپیوٹر سائنس کے ذیلی فیلڈ کے مرکز میں یہی سوال ہے جسے کمپیوٹیشنل کمپلیکٹی تھیوری کہا جاتا ہے۔ اس کا جواب دینا مشکل سوال ہے، لیکن اسے پلٹائیں اور یہ آسان ہو جاتا ہے۔ بدترین نقطہ نظر تقریبا ہمیشہ آزمائش اور غلطی ہے، جس میں ممکنہ حل میں پلگ ان کرنا شامل ہے جب تک کہ کوئی کام نہیں کرتا. لیکن کچھ مسائل کے لیے، ایسا لگتا ہے کہ کوئی متبادل نہیں ہے - بدترین نقطہ نظر بھی بہترین ہے۔

محققین نے طویل عرصے سے سوچا ہے کہ کیا واقعی ایسا ہوتا ہے، کہا راہول ایلانگو، میساچوسٹس انسٹی ٹیوٹ آف ٹیکنالوجی میں پیچیدگی تھیوری کا مطالعہ کرنے والا ایک گریجویٹ طالب علم۔ "آپ پوچھ سکتے ہیں، 'کیا ایسے مسائل ہیں جن کے لیے اندازہ لگانا اور چیک کرنا ہی مناسب ہے؟'"

کمپلیکسیٹی تھیورسٹوں نے بہت سے کمپیوٹیشنل مسائل کا مطالعہ کیا ہے، اور یہاں تک کہ مشکل لوگ بھی اکثر کسی نہ کسی طرح کے ہوشیار طریقہ کار، یا الگورتھم کو تسلیم کرتے ہیں، جو خالص آزمائش اور غلطی سے حل تلاش کرنا تھوڑا آسان بنا دیتا ہے۔ چند مستثنیات میں نام نہاد کمپریشن مسائل ہیں، جہاں مقصد ڈیٹا سیٹ کی مختصر ترین تفصیل تلاش کرنا ہے۔

لیکن گزشتہ نومبر میں محققین کے دو گروہ آزادانہ طور پر دریافت کمپریشن کے مسائل کے لیے ایک اور الگورتھم - ایک جو تمام ممکنہ جوابات کی جانچ پڑتال سے کہیں زیادہ تیز ہے۔ نیا نقطہ نظر ایک الگورتھم کو اپنانے کے ذریعے کام کرتا ہے جو 25 سال قبل خفیہ نگاروں کے ذریعہ ایک مختلف مسئلہ پر حملہ کرنے کے لیے ایجاد کیا گیا تھا۔ صرف ایک پابندی ہے: آپ کو الگورتھم کو اپنے ڈیٹا سیٹ کے سائز کے مطابق بنانے کی ضرورت ہے۔

"وہ واقعی خوبصورت اور اہم نتائج ہیں،" کہا ایرک ایلینڈر، Rutgers یونیورسٹی میں ایک نظریاتی کمپیوٹر سائنس دان۔

سختی کی تعریف

نئے نتائج پیچیدگی کے نظریہ کی آمد سے پہلے سوویت یونین میں پہلے مطالعہ کیے گئے سوال کی تحقیقات کے لیے تازہ ترین ہیں۔ "میں گریڈ اسکول میں تھا اس سے پہلے، روس میں لوگ اسے وضع کر رہے تھے،" آلینڈر نے کہا۔

وہ مخصوص کمپیوٹیشنل مسئلہ جس کا ان سوویت محققین نے مطالعہ کیا، جسے کم از کم سرکٹ سائز کا مسئلہ کہا جاتا ہے، ایک ایسا ہی ہے جس کا کمپیوٹر ہارڈویئر کے ڈیزائنرز کو ہر وقت سامنا کرنا پڑتا ہے۔ اگر آپ کو مکمل وضاحتیں دی گئی ہیں کہ الیکٹرانک سرکٹ کیسا برتاؤ کرنا چاہیے، تو کیا آپ سب سے آسان سرکٹ تلاش کر سکتے ہیں جو کام کرے گا؟ کوئی بھی نہیں جانتا تھا کہ اس مسئلے کو "پیریبر" کے بغیر کیسے حل کیا جائے - ایک روسی لفظ جو تقریباً "مکمل تلاش" کے مترادف ہے۔

کم سے کم سرکٹ سائز کا مسئلہ کمپریشن کے مسئلے کی ایک مثال ہے۔ آپ ایک سرکٹ کے رویے کو بٹس کی ایک لمبی تار کے ساتھ بیان کر سکتے ہیں — 0s اور 1s — اور پھر پوچھیں کہ کیا کم بٹس کا استعمال کرتے ہوئے اسی رویے کو دوبارہ پیدا کرنے کا کوئی طریقہ ہے؟ تمام ممکنہ سرکٹ لے آؤٹس کو چیک کرنے میں وقت لگے گا جو سٹرنگ میں بٹس کی تعداد کے ساتھ تیزی سے بڑھتا ہے۔

اس قسم کی کفایتی نمو ایک مشکل کمپیوٹیشنل مسئلہ کی وضاحتی خصوصیت ہے۔ لیکن تمام مشکل مسائل یکساں طور پر مشکل نہیں ہوتے ہیں — کچھ کے الگورتھم ہوتے ہیں جو مکمل تلاش سے زیادہ تیز ہوتے ہیں، حالانکہ ان کے رن ٹائم اب بھی تیزی سے بڑھتے ہیں۔ جدید اصطلاحات میں، perebor سوال یہ ہے کہ آیا کمپریشن کے مسائل کے لیے کوئی ایسا الگورتھم موجود ہے؟

1959 میں، سرگئی یابلونسکی نامی ایک ممتاز محقق نے یہ ثابت کرنے کا دعویٰ کیا کہ کم از کم سرکٹ سائز کے مسئلے کو حل کرنے کا واقعی مکمل تلاش ہی واحد طریقہ ہے۔ لیکن اس کے ثبوت نے کچھ خامیاں چھوڑی ہیں۔ کچھ محققین نے اس وقت خامیوں کو دیکھا، لیکن یابلونسکی کافی اثر و رسوخ رکھتے تھے کہ زیادہ تر دوسروں کو پیریبر کے سوال پر کام کرنے سے روک سکے۔

اس کے بعد کی دہائیوں میں، چند محققین نے کمپریشن کے مسائل کا مطالعہ کیا، اور پیریبر سوال کو زیادہ تر پیچیدگی تھیوری کی قبل از تاریخ میں فوٹ نوٹ کے طور پر جانا جاتا تھا۔ اس سوال پر بڑے پیمانے پر توجہ حال ہی میں اس وقت آئی جب محققین نے کمپریشن کے مسائل اور خفیہ نگاری کی بنیادوں کے درمیان ایک دلچسپ تعلق دریافت کیا۔

یک طرفہ ٹریفک

جدید خفیہ نگاری خفیہ پیغامات کی حفاظت کے لیے سخت کمپیوٹیشنل مسائل کا استعمال کرتی ہے۔ لیکن کمپیوٹیشنل سختی صرف اس صورت میں مفید ہے جب یہ غیر متناسب ہو — اگر کوڈ شدہ پیغامات کو سمجھنا مشکل ہے لیکن پیغامات کو پہلے انکوڈ کرنا مشکل نہیں ہے۔

ہر کرپٹوگرافی اسکیم میں، اس اسمیٹری کی اصل ایک ریاضیاتی چیز ہے جسے یک طرفہ فنکشن کہا جاتا ہے، جو ان پٹ بٹ سٹرنگز کو اسی لمبائی کے آؤٹ پٹ سٹرنگز میں تبدیل کرتا ہے۔ ایک طرفہ فنکشن کو ان پٹ دیے جانے سے، آؤٹ پٹ کا حساب لگانا آسان ہے، لیکن آؤٹ پٹ دینے سے فنکشن کو الٹنا مشکل ہے - یعنی اسے ریورس انجینئر کرنا اور ان پٹ کو بازیافت کرنا۔

ایلینڈر نے کہا، "کرپٹوگرافرز واقعی بہت، بہت مؤثر طریقے سے کمپیوٹیبل ون وے فنکشنز رکھنا چاہیں گے جو واقعی، الٹنا بہت مشکل ہیں۔" ایسا لگتا ہے کہ بہت سے ریاضی کے افعال میں یہ خاصیت ہے، اور ان افعال کو الٹنے کی دشواری مختلف کمپیوٹیشنل مسائل کو حل کرنے میں ظاہری مشکل سے پیدا ہوتی ہے۔

بدقسمتی سے، کرپٹو گرافرز یقینی طور پر نہیں جانتے کہ آیا ان میں سے کسی بھی فنکشن کو الٹنا واقعی مشکل ہے — درحقیقت، یہ ممکن ہے کہ حقیقی یک طرفہ افعال موجود نہ ہوں۔ یہ غیر یقینی صورتحال برقرار ہے کیونکہ پیچیدگی تھیوریسٹوں کے پاس ہے۔ 50 سال جدوجہد کی۔ یہ ثابت کرنا کہ بظاہر مشکل مسائل واقعی مشکل ہیں۔ اگر وہ نہیں ہیں، اور اگر محققین ان مسائل کے لیے انتہائی تیز رفتار الگورتھم دریافت کرتے ہیں، تو یہ کرپٹوگرافی کے لیے تباہ کن ہوگا - یکطرفہ سڑک پر دونوں سمتوں میں تیز رفتار کاروں کو اچانک روٹ کرنے کے مترادف۔

اگرچہ کمپیوٹیشنل سختی کے بارے میں ایک جامع تفہیم مضمر ہے، حال ہی میں خفیہ نگاروں نے یکطرفہ افعال کے متحد نظریہ کی طرف دلچسپ پیش رفت کی ہے۔ 2020 میں ایک بڑا قدم اٹھایا گیا، جب تل ابیب یونیورسٹی کے کرپٹوگرافر رافیل پاس۔ اور اس کا گریجویٹ طالب علم یانی لیو ثابت ہوا کہ یک طرفہ افعال ہیں۔ قریبی طور پر منسلک ایک مخصوص کمپریشن مسئلے کے لیے جسے وقتی پابند کولموگوروف پیچیدگی کا مسئلہ کہا جاتا ہے۔

اگر وہ ایک مسئلہ زیادہ تر ان پٹس کے لیے حل کرنا واقعی مشکل ہے، تو پاس اور لیو کے نتیجے سے ایک ایسا نسخہ ملتا ہے کہ کس طرح ایک سخت ون وے فنکشن بنایا جائے — جو کہ محفوظ ہونے کی گارنٹی ہے چاہے دوسرے کمپیوٹیشنل مسائل کہیں زیادہ آسان کیوں نہ ہوں۔ محققین کی توقع سے زیادہ. لیکن اگر وقتی پابند کولموگوروف کی پیچیدگی کے مسئلے کو حل کرنے کے لیے ایک تیز الگورتھم موجود ہے، تو خفیہ نگاری برباد ہو جاتی ہے، اور کوئی بھی فنکشن آسانی سے الٹا جا سکتا ہے۔ اس مسئلے کی سختی پر مبنی ایک طرفہ فنکشن سب سے زیادہ محفوظ فنکشن ہے - ان سب پر حکمرانی کے لیے ایک طرفہ فنکشن۔

ڈیٹا کے ڈھانچے پر تعمیر

پاس اور لیو کی دریافت تحقیق کی ایک لمبی لائن کا تازہ ترین باب تھا جو خفیہ نگاری کی بنیادوں کو بہتر طور پر سمجھنے کے لیے پیچیدگی تھیوری کا استعمال کرتا ہے۔ لیکن اس نے اس رشتے کو الٹنے کا ایک طریقہ بھی تجویز کیا: وقت کے پابند کولموگوروف پیچیدگی کے مسئلے اور فنکشن کے الٹ جانے کے درمیان مساوات کا مطلب یہ ہے کہ دونوں میں سے کسی ایک مسئلے کے بارے میں بصیرت دوسرے کے بارے میں مزید انکشاف کر سکتی ہے۔ کرپٹوگرافرز اپنے خفیہ کاری کے طریقوں کے کمزور نکات کو بہتر طور پر سمجھنے کے لیے کئی دہائیوں سے فنکشن انورسیشن الگورتھم کا مطالعہ کر رہے ہیں۔ محققین نے سوچنا شروع کیا کہ آیا وہ الگورتھم پیچیدگی تھیوری میں پرانے سوالات کے جوابات دینے میں مدد کرسکتے ہیں۔

بہت سے کمپیوٹیشنل مسائل کی طرح، فنکشن الٹنے کو مکمل تلاش کے ذریعے حل کیا جا سکتا ہے۔ آؤٹ پٹ سٹرنگ کو دیکھتے ہوئے، ہر ممکنہ ان پٹ کو فنکشن میں اس وقت تک لگائیں جب تک کہ آپ کو صحیح جواب نہ ملے۔

1980 میں، کرپٹوگرافر مارٹن ہیل مین نے اس بات کا مطالعہ کرنا شروع کیا کہ آیا اس سے بہتر کرنا ممکن ہے - وہی سوال جو سوویت ریاضی دانوں نے دہائیوں پہلے کمپریشن کے مسائل کے بارے میں پوچھا تھا۔ ہیل مین دریافت کہ ہاں، یہ ممکن ہے — جب تک کہ آپ ڈیٹا سٹرکچر کہلانے والی ریاضیاتی اشیاء کا استعمال کرتے ہوئے پہلے سے کچھ اضافی کام کرنے کے لیے تیار ہوں۔

ڈیٹا سٹرکچر بنیادی طور پر ایک ٹیبل ہوتا ہے جو الٹا ہونے والے فنکشن کے بارے میں معلومات کو محفوظ کرتا ہے، اور کسی کو بنانے کے لیے فنکشن کے آؤٹ پٹس کو کچھ اسٹریٹجک طور پر منتخب کردہ ان پٹس کی کمپیوٹنگ کی ضرورت ہوتی ہے۔ ان تمام حسابات میں "بہت لمبا وقت لگ سکتا ہے،" نے کہا ریان ولیمز، MIT میں ایک پیچیدگی تھیوریسٹ۔ "لیکن خیال یہ ہے کہ یہ ایک بار، ایک بار اور ہمیشہ کے لیے کیا جاتا ہے۔" اگر آپ ایک ہی فنکشن کو الٹنے کی کوشش کر رہے ہیں جس میں بہت سے مختلف آؤٹ پٹس ہیں — کہیے، اسی طرح سے انکرپٹ کیے گئے بہت سے مختلف پیغامات کو ڈی کوڈ کرنے کے لیے — پہلے سے یہ کام کرنا فائدہ مند ہو سکتا ہے۔

بلاشبہ، اس اضافی معلومات کو ذخیرہ کرنے کے لیے جگہ کی ضرورت ہوتی ہے، لہذا اس حکمت عملی کو انتہائی حد تک لے جائیں، اور آپ ایک تیز رفتار پروگرام کے ساتھ ختم ہو سکتے ہیں جو کسی بھی کمپیوٹر پر فٹ نہیں ہو سکتا۔ Hellman نے ایک ہوشیار ڈیٹا ڈھانچہ ڈیزائن کیا جس نے اس کے الگورتھم کو زیادہ سے زیادہ جگہ لینے کے بغیر مکمل تلاش کے مقابلے میں زیادہ تر افعال کو قدرے تیزی سے الٹنے کے قابل بنایا۔ پھر 2000 میں، خفیہ نگاروں Amos Fiat اور Moni Naor توسیع تمام افعال کے لیے Hellman کے دلائل۔

2020 میں پاس اور لیو کی پیش رفت کے بعد، یہ پرانے نتائج اچانک نئے متعلقہ ہو گئے۔ Fiat-Naor الگورتھم مکمل تلاش سے زیادہ تیزی سے صوابدیدی افعال کو الٹ سکتا ہے۔ کیا یہ کمپریشن کے مسائل کے لیے بھی کام کر سکتا ہے؟

وردی سے باہر

سوال اٹھانے والے پہلے محققین پیچیدگی تھیوریسٹ تھے۔ راہل سنتھانم آکسفورڈ یونیورسٹی کا اور اس کا گریجویٹ طالب علم ہینلن رین. انہوں نے ایک میں ایسا کیا۔ 2021 کاغذ یہ ثابت کرنا کہ کمپریشن کے مسائل اور فنکشن الٹا اس سے کہیں زیادہ ایک دوسرے سے جڑے ہوئے تھے جتنا کہ محققین نے محسوس کیا تھا۔

پاس اور لیو نے ثابت کیا تھا کہ اگر وقتی پابند کولموگوروف پیچیدگی کا مسئلہ مشکل ہے، تو فنکشن کا الٹا بھی سخت ہونا چاہیے، اور اس کے برعکس۔ لیکن مسائل مشکل ہوسکتے ہیں اور پھر بھی ان حلوں کو تسلیم کرتے ہیں جو مکمل تلاش سے تھوڑا بہتر ہیں۔ سنتھانم اور رین نے ظاہر کیا کہ آیا ایک مسئلہ کے لیے مکمل تلاش کی ضرورت ہے اور کیا دوسرے کے لیے اس کی ضرورت ہے کے درمیان گہرا تعلق ہے۔

ان کے نتیجے میں الگورتھم کی دو وسیع کلاسوں کے لیے مختلف مضمرات تھے جن کا محققین اکثر مطالعہ کرتے ہیں، جنہیں "یکساں" اور "غیر یونیفارم" الگورتھم کہتے ہیں۔ یکساں الگورتھم ہر ان پٹ کے لیے ایک ہی طریقہ کار کی پیروی کرتے ہیں — نمبروں کی فہرستوں کو ترتیب دینے کے لیے ایک یکساں پروگرام، مثال کے طور پر، اسی طرح کام کرے گا چاہے فہرست میں 20 اندراجات ہوں یا 20,000۔ غیر یکساں الگورتھم اس کے بجائے مختلف طوالت کے ان پٹ کے لیے مختلف طریقہ کار استعمال کرتے ہیں۔

Fiat-Naor الگورتھم کے ذریعہ استعمال کردہ ڈیٹا ڈھانچے ہمیشہ ایک مخصوص فنکشن کے مطابق بنائے جاتے ہیں۔ کسی ایسے فنکشن کو الٹنے کے لیے جو 10 بٹ اسٹرنگ کو گھماتا ہے، آپ کو ڈیٹا سٹرکچر کی ضرورت ہوتی ہے جو اس فنکشن سے مختلف ہو جو آپ کو 20 بٹ سٹرنگ کو اسکریبل کرنے والے فنکشن کو الٹنے کی ضرورت ہو، خواہ اسکرمبلنگ اسی طرح کی گئی ہو۔ یہ Fiat-Naor کو غیر یکساں الگورتھم بناتا ہے۔

سنتھانم اور رین کے نتیجے نے تجویز کیا کہ کمپریشن کے مسائل کو حل کرنے کے لیے Fiat-Naor الگورتھم کو الگورتھم میں تبدیل کرنا ممکن ہے۔ لیکن الگورتھم کو ایک مسئلہ سے دوسرے میں ڈھالنا سیدھا نہیں تھا، اور انہوں نے اس سوال کو مزید آگے نہیں بڑھایا۔

ایک سال بعد پاس نے اسی خیال سے ٹھوکر کھائی، Fiat کو ایک ورکشاپ میں کلاسک الگورتھم کے بارے میں گفتگو سننے کے بعد، جس میں خفیہ نگاری میں Naor کے تعاون کا جشن منایا جا رہا تھا۔ انہوں نے کہا کہ "فنکشن الٹا استعمال کرنے کا یہ خیال تب سے میرے ذہن میں تھا۔ بعد میں اس نے تل ابیب یونیورسٹی کے محقق کے ساتھ اس مسئلے پر سنجیدگی سے کام کرنا شروع کیا۔ نوم مازور.

دریں اثنا، Ilango کیلیفورنیا کے برکلے میں سائمن انسٹی ٹیوٹ فار دی تھیوری آف کمپیوٹنگ کے دورے پر سنتھانم سمیت دیگر محققین کے ساتھ بات چیت کے بعد اس مسئلے پر حملہ کرنے کے لیے متاثر ہوا۔ سنتھانم نے کہا، "یہ ان میں سے ایک بہت ہی بے تکی گفتگو سے نکلا ہے جہاں آپ صرف چیزوں کو ادھر ادھر پھینک رہے ہیں۔" Ilango بعد میں ولیمز اور کے ساتھ افواج میں شمولیت اختیار کی شوچی ہیرہارا، ٹوکیو میں نیشنل انسٹی ٹیوٹ آف انفارمیٹکس میں ایک پیچیدگی تھیوریسٹ۔

مشکل حصہ یہ معلوم کرنا تھا کہ کس طرح Fiat-Naor الگورتھم کے مرکز میں ڈیٹا ڈھانچے کو کمپریشن کے مسائل کو حل کرنے کے لیے غیر یکساں الگورتھم میں سرایت کرنا ہے۔ اس قسم کی سرایت کرنے کے لیے ایک معیاری طریقہ کار موجود ہے، لیکن یہ الگورتھم کو سست کر دے گا، اور مکمل تلاش پر اس کا فائدہ ختم کر دے گا۔ دونوں ٹیموں نے Fiat-Naor ڈیٹا ڈھانچے کو شامل کرنے کے ہوشیار طریقے تلاش کیے، اور کمپریشن کے مسائل کے لیے الگورتھم حاصل کیے جو تمام ان پٹ پر کام کرتے تھے اور مکمل تلاش سے زیادہ تیز رہتے تھے۔

دونوں الگورتھم کی تفصیلات قدرے مختلف ہیں۔ Ilango اور اس کے ساتھی مصنفین کی طرف سے ایک مکمل تلاش سے زیادہ تیز ہے یہاں تک کہ اگر آپ تلاش کو آسان ترین امکانات تک محدود کر دیتے ہیں، اور یہ تمام کمپریشن مسائل پر لاگو ہوتا ہے — وقت کی پابند کولموگوروف کی پیچیدگی، کم از کم سرکٹ سائز کا مسئلہ، اور بہت سے دوسرے۔ لیکن بنیادی خیال دونوں الگورتھم کے لیے ایک جیسا تھا۔ خفیہ نگاری کی تکنیکوں نے اس نئے ڈومین میں اپنی اہمیت ثابت کر دی تھی۔

الٹا کنورجنسی

غیر یکساں الگورتھم کا نیا ثبوت ایک فطری سوال اٹھاتا ہے: یکساں الگورتھم کا کیا ہوگا؟ کیا کمپریشن کے مسائل کو ان کا استعمال کرتے ہوئے مکمل تلاش سے زیادہ تیزی سے حل کرنے کا کوئی طریقہ ہے؟

نتائج کی حالیہ سٹرنگ سے یہ ظاہر ہوتا ہے کہ ایسا کوئی بھی الگورتھم صوابدیدی افعال کو الٹانے کے لیے یکساں الگورتھم کے مترادف ہو گا - ایسی چیز جس کی خفیہ نگاروں نے دہائیوں سے ناکام کوشش کی ہے۔ اس کی وجہ سے، بہت سے محققین کو امکان نہیں ہے.

’’میں بہت حیران رہوں گا،‘‘ سنتھانم نے کہا۔ "اس کے لیے بالکل نئے آئیڈیا کی ضرورت ہوگی۔"

لیکن ایلینڈر نے کہا کہ محققین کو امکان کو کم نہیں کرنا چاہئے۔ "میرے لیے ایک اچھا کام کرنے والا مفروضہ یہ رہا ہے کہ اگر کچھ کرنے کا کوئی غیر یکساں طریقہ ہے، تو بہت امکان ہے کہ یکساں طریقہ ہو،" انہوں نے کہا۔

کسی بھی طرح سے، اس کام نے پیچیدگی کے نظریہ سازوں کو خفیہ نگاری کے پرانے سوالات میں نئی ​​دلچسپی پیدا کر دی ہے۔ یوول ایشائیاسرائیل کے حیفہ میں ٹیکنین کے ایک کرپٹوگرافر نے کہا کہ یہی چیز اسے سب سے زیادہ پرجوش بناتی ہے۔

انہوں نے کہا کہ "میں مختلف کمیونٹیز کے درمیان دلچسپی کے اس ہم آہنگی کو دیکھ کر بہت خوش ہوں۔ "میرے خیال میں یہ سائنس کے لیے بہت اچھا ہے۔"