پیچیدگی تھیوری کا 50 سالہ سفر علم کی حدود تک | کوانٹا میگزین

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

"اس نے مجھے بیٹھنے اور توجہ دینے پر مجبور کیا،" یاد کیا۔ کارموسینو، اب IBM میں ایک نظریاتی کمپیوٹر سائنس دان ہے۔ اس نے کرٹ گوڈل کے کام پر ایک اختیاری سیمینار کے لیے سائن اپ کیا، جس کے خود ساختہ دلائل نے سب سے پہلے ریاضیاتی استدلال کی حدود کو بے نقاب کیا اور حساب کی بنیادی حدود پر مستقبل کے تمام کاموں کی بنیاد بنائی۔ اس میں لینے کے لئے بہت کچھ تھا۔

"میں 100٪ سمجھ نہیں پایا،" کارموسینو نے کہا۔ "لیکن میں جانتا تھا کہ میں چاہتا ہوں۔"

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

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

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

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

"آپ سوچ سکتے ہیں، 'ٹھیک ہے، یہ بہت اچھا ہے۔ ہوسکتا ہے کہ پیچیدگی کے نظریہ ساز پاگل ہو گئے ہوں،'' کہا راہول ایلانگو, MIT میں ایک گریجویٹ طالب علم جس نے میدان میں کچھ انتہائی دلچسپ حالیہ نتائج پیش کیے ہیں۔

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

"یہ واضح ہو گیا ہے کہ میٹا پیچیدگی چیزوں کے دل کے قریب ہے،" کہا سکاٹ ایرونسنیونیورسٹی آف ٹیکساس، آسٹن میں ایک پیچیدگی تھیوریسٹ۔

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

معلوم نامعلوم

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

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

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

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

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

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

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

محققین نے ابھی تک امید ظاہر کی ہے کہ ریاضی کا مستقبل کا نظریہ، اگرچہ ضروری طور پر نامکمل ہے، تاہم اس کے باوجود فیصلہ کن ثابت ہو سکتا ہے۔ شاید وہ ایسا طریقہ کار تیار کر سکتے ہیں جو Gödel's جیسی ناگوار تجاویز سے پرہیز کرتے ہوئے تمام ثابت شدہ بیانات کی نشاندہی کر سکیں۔ مصیبت یہ تھی کہ کوئی نہیں جانتا تھا کہ ان فرضی طریقہ کار کے بارے میں کیسے استدلال کیا جائے۔

پھر 1936 میں، ایلن ٹورنگ نامی ایک 23 سالہ گریجویٹ طالب علم نے حساب کی اس وقت کی غیر مانوس زبان میں ہلبرٹ کی فیصلہ کن حالت کو دوبارہ بیان کیا اور اسے ایک مہلک دھچکا سمجھا۔ ٹورنگ نے ایک ریاضیاتی ماڈل تیار کیا - جسے اب کے نام سے جانا جاتا ہے۔ ٹورنگ مشین - جو تمام ممکنہ الگورتھم کی نمائندگی کر سکتا ہے، اور یہ ظاہر کرتا ہے کہ اگر ہلبرٹ کا طریقہ کار موجود ہے، تو یہ اس ماڈل میں فٹ ہو جائے گا۔ اس کے بعد اس نے خود حوالہ کے طریقے استعمال کیے جیسے Gödel's to ثابت ناقابل فیصلہ بیانات کا وجود - یا، مساوی طور پر، ناقابل حساب مسائل جن کو کوئی الگورتھم حل نہیں کرسکتا۔

ہلبرٹ کا پروگرام کھنڈرات میں پڑا: ہمیشہ کے لئے اس بات کی بنیادی حدود ہوں گی کہ کیا ثابت کیا جاسکتا ہے اور کیا شمار کیا جاسکتا ہے۔ لیکن جیسے جیسے کمپیوٹر نظریاتی تجرید سے حقیقی مشینوں کی طرف تیار ہوئے، محققین نے محسوس کیا کہ ٹیورنگ کے قابل حل اور ناقابل حل مسائل کے درمیان سادہ فرق نے بہت سے سوالات کو جواب نہیں دیا۔

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

کارموسینو نے کہا کہ "ایک بھرپور نظریہ ابھرتا ہے، اور ہمیں اب جوابات کا علم نہیں ہے۔"

مختلف راستے

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

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

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

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

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

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

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

Hamiltonian path مسئلہ اور Eulerian path مسئلہ دونوں پیچیدگی کلاس NP میں ہیں، ان تمام مسائل کو شامل کرنے کے لیے بیان کیا گیا ہے جن کے حل کو کثیر الجہتی الگورتھم کے ذریعے چیک کیا جا سکتا ہے۔ یولیرین پاتھ کا مسئلہ بھی کلاس P میں آتا ہے کیونکہ ایک کثیر الجہتی الگورتھم اسے حل کر سکتا ہے، لیکن تمام ظہور کے لیے، یہ ہیملٹونین پاتھ کے مسئلے کے لیے درست نہیں ہے۔ یہ دونوں گراف کے مسائل، اتنے سطحی طور پر ایک جیسے، اتنے ڈرامائی طور پر مختلف کیوں ہیں؟ یہ P بمقابلہ NP مسئلہ کا نچوڑ ہے۔

عالمی طور پر سخت

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

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

کک کو شبہ تھا کہ اس کے عالمگیر مسئلے کے لیے کوئی تیز الگورتھم نہیں ہے، اور اس نے کاغذ کے وسط میں اتنا ہی کہا، "میں محسوس کرتا ہوں کہ اس قیاس کو ثابت کرنے کی کوشش میں کافی محنت کرنا قابل قدر ہے۔" "کافی کوشش" ایک چھوٹی بات ثابت ہوگی۔

اسی وقت کے ارد گرد، سوویت یونین میں ایک گریجویٹ طالب علم کا نام لیونیڈ لیون ثابت کیا a اسی طرح کا نتیجہسوائے اس کے کہ اس نے کئی مختلف عالمگیر مسائل کی نشاندہی کی۔ اس کے علاوہ، امریکی پیچیدگی تھیوریسٹ رچرڈ کارپ ثابت ہوا کہ کک (اور لیون، حالانکہ کارپ اور کک کو کئی سالوں بعد تک لیون کے کام کے بارے میں معلوم نہیں تھا) کی طرف سے شناخت کی گئی عالمگیریت کی خاصیت خود عالمگیر تھی۔ تقریباً ہر NP مسئلہ بغیر کسی معروف کثیر الجہتی الگورتھم کے — یعنی تقریباً ہر آسانی سے جانچنے کے قابل مسئلہ جو مشکل لگتا تھا — میں ایک ہی خاصیت تھی، جو NP-completeness کے نام سے مشہور ہوئی۔

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

کسی بھی NP-مکمل مسئلے کی مشکل کو حل کرنا P بمقابلہ NP سوال کو حل کرنے کے لیے کافی ہوگا۔ اگر P ≠ NP ہے تو، آسان اور مشکل مسائل کے درمیان فرق ہزاروں کالموں کے ذریعے رکھا جاتا ہے جو تمام یکساں طور پر مضبوط ہیں۔ اگر P = NP، تو پوری عمارت گرنے کے دہانے پر کھڑی ہے، صرف ایک ٹکڑے کے گرنے کا انتظار ہے۔

کک، لیون اور کارپ نے متحد کر دیا تھا جو بہت سے غیر متعلقہ مسائل کی طرح لگتا تھا۔ اب تمام پیچیدگی تھیورسٹوں کو ایک مسئلہ حل کرنا تھا: کیا P = NP ہے یا نہیں؟

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

فرض کریں کہ P = NP۔ اسے ثابت کرنے کے لیے، محققین کو NP-مکمل مسئلے کے لیے ایک تیز الگورتھم تلاش کرنے کی ضرورت ہوگی، جو اس وسیع زمین کی تزئین کے کسی غیر واضح کونے میں چھپا ہوا ہو گا۔ اس بات کی کوئی گارنٹی نہیں ہے کہ وہ اسے کسی بھی وقت جلد ہی تلاش کر لیں گے: پیچیدگی تھیوریسٹ کبھی کبھار کرتے ہیں۔ دریافت کئی دہائیوں کے کام کے بعد ہی بظاہر مشکل (حالانکہ NP-مکمل نہیں) مسائل کے لیے ذہین الگورتھم۔

اب فرض کریں کہ P ≠ NP۔ یہ ثابت کرنا اور بھی مشکل لگتا ہے۔ پیچیدگی کے نظریہ سازوں کو یہ قائم کرنا پڑے گا کہ کوئی تیز رفتار الگورتھم ممکنہ طور پر موجود نہیں ہوسکتا ہے، جو مستقبل کے تمام محققین کی بہترین کاوشوں کو مؤثر طریقے سے متوقع اور ناکام بناتا ہے۔

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

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

"میں نے سوچا، 'واہ، مجھے اسے سنجیدگی سے لینے کی ضرورت ہے،'" کارموسینو نے یاد کیا۔ کچھ ہی دیر میں، وہ اس موضوع میں اتنا مگن تھا کہ اس کے سرپرست نے نرمی سے مشورہ دیا کہ وہ اپنے پوسٹ گریجویشن کے منصوبوں پر نظر ثانی کریں۔

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

کارموسینو کا بنیادی مقصد، شروع میں، بہتر طور پر سمجھنا تھا۔ تاریخی کاغذ دو دہائیاں پہلے سے جس نے اس کے تخیل کو اپنی گرفت میں لے لیا تھا۔ وہ کاغذ، پیچیدگی تھیوریسٹوں کے ذریعہ الیگزینڈر رازبوروف اور سٹیون روڈچنے ظاہر کیا تھا کہ P ≠ NP کو ثابت کرنے کے لیے ایک خاص "قدرتی" حکمت عملی تقریباً ناکام ہو جائے گی، کیونکہ کامیابی ایک بھاری قیمت پر آئے گی — خفیہ نگاری کی مکمل خرابی — جسے محققین بہت کم سمجھتے ہیں۔ محققین نے Razborov اور Rudich کے نتیجے کو P ≠ NP ثابت کرنے کے اس مقبول انداز میں رکاوٹ کے طور پر سمجھا۔

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

الانگو نے کہا، "پیچیدگی کا نظریہ لعنتی بھی ہے اور بہت سی رکاوٹوں سے نوازا گیا ہے۔"

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

لیکن میٹا پیچیدگی میں قدرتی ثبوت کی رکاوٹ سے پگڈنڈی کی پیروی کرنے کے لیے، ہمیں واپس وہاں جانا پڑے گا جہاں ہم نے 1970 کی دہائی میں محققین کو چھوڑا تھا، جب انہوں نے پہلی بار P بمقابلہ NP مسئلے سے نمٹنا شروع کیا تھا۔ کس چیز نے مسائل کو مشکل ثابت کرنا اتنا مشکل بنا دیا؟

ایک گردشی راستہ

سب سے پہلے، محققین نے P ≠ NP کو ثابت کرنے کی کوشش کی — یعنی یہ ثابت کریں کہ NP کے کچھ مسائل کسی بھی ممکنہ کثیر الثانی الگورتھم کے ذریعے حل نہیں کیے جا سکتے — ٹیورنگ نے یہ ثابت کرنے کے لیے استعمال کیا تھا کہ کچھ مسائل کسی بھی الگورتھم کے ذریعے حل نہیں کیے جا سکتے۔ . لیکن وہ جلدی دریافت اس بات کا ثبوت کہ وہ طریقے کام نہیں کریں گے — P بمقابلہ NP سوال کو حل کرنے میں پہلی بڑی رکاوٹ۔ لہذا انہوں نے ایک اور نقطہ نظر تلاش کرنا شروع کیا، اور انہیں جلد ہی ٹیورنگ کے معاصر کے کام میں مل گیا۔ کلاڈ شنن.

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

ان اظہارات میں، بولین متغیرات "منطق دروازے" اور، یا اور نہیں کے ذریعہ ایک دوسرے سے منسلک ہوتے ہیں۔ ابتدائی اظہار A اور B، مثال کے طور پر، درست ہے جب A اور B دونوں صحیح ہیں، اور دوسری صورت میں غلط؛ دوسری طرف، A OR B درست ہے اگر دو متغیرات میں سے کم از کم ایک درست ہے۔ ایک نہیں گیٹ اس سے بھی آسان ہے: یہ ایک واحد متغیر کی قدر کو الٹ دیتا ہے۔ ان بنیادی بلڈنگ بلاکس میں سے کافی کے ساتھ، آپ کوئی بھی حساب کتاب کر سکتے ہیں۔

"جب آپ اپنے کمپیوٹر کو دیکھتے ہیں، دن کے اختتام پر، یہ کیا کر رہا ہے؟ یہ ایک سرکٹ چلا رہا ہے، "ایلانگو نے کہا۔

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

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

"میری سمجھ یہ ہے کہ لوگوں نے سرکٹ کی پیچیدگی پر کام کرنا شروع کیا کیونکہ انہوں نے فیصلہ کیا کہ ٹورنگ مشینیں بہت پیچیدہ ہیں،" کہا۔ ریان ولیمز، MIT میں ایک پیچیدگی تھیوریسٹ۔ "ہم سرکٹس گیٹ بہ گیٹ کا مطالعہ کر سکتے ہیں۔"

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

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

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

یہ وہ حکمت عملی تھی جس پر 1980 کی دہائی میں زیادہ تر پیچیدگی کے نظریہ سازوں نے عمل کیا۔ اور مشکلات ان کی طرف تھیں۔ شینن کے پاس تھا۔ ثابت ہوا 1949 میں کہ تقریباً ہر بولین سچ ٹیبل (جو کہ مقررہ سائز کے بولین فنکشن کے تمام ممکنہ ان پٹ اور آؤٹ پٹس کی صرف ایک لمبی فہرست ہے) میں سرکٹ کی پیچیدگی ہے جو عملی طور پر زیادہ سے زیادہ ہے۔ اس نے ایک حیرت انگیز طور پر سادہ دلیل کا استعمال کیا: بہت سے دروازوں کو جوڑنے کے طریقے سے بہت کم گیٹس کو جوڑنے کے طریقے بہت کم ہیں۔

ایرونسن نے کہا کہ "اس کے ارد گرد جانے کے لیے کافی چھوٹے سرکٹس نہیں ہیں۔

لہذا پیچیدگی کے نظریہ سازوں نے خود کو ایک متجسس صورتحال میں پایا۔ اگر تقریباً ہر سچ ٹیبل میں سرکٹ کی پیچیدگی زیادہ ہے، تو تقریباً ہر بولین فنکشن کا حساب لگانا مشکل ہونا چاہیے۔ محققین کو صرف ایک ایسے فنکشن کی شناخت کرنی تھی جو کلاس NP میں بھی جانا جاتا تھا۔ یہ کتنا مشکل ہو سکتا ہے؟

کرپٹو برادرز

سب سے پہلے، ترقی تیز تھی. 1981 میں، Sipser اور دو ساتھیوں ثابت ہوا کہ ایک خاص بولین فنکشن کی گنتی کرنا یقینی طور پر مشکل تھا اگر وہ سرکٹس کا استعمال کرتے ہیں جن پر کچھ پابندیاں ہوتی ہیں کہ گیٹس کو کیسے ترتیب دیا جاسکتا ہے۔

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

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

رازبوروف نے کہا کہ میں خوش قسمت تھا کہ مجھے نہیں معلوم تھا کہ یہ مسئلہ کتنا مشکل ہے۔ "ورنہ شاید میں شروع بھی نہ کرتا۔"

رازبوروف نے صرف AND اور OR گیٹس پر مشتمل سرکٹس کا تجزیہ کیا، اور ثابت ہوا کہ اس طرح کے سرکٹس کا استعمال کرتے ہوئے کسی خاص فنکشن کا حساب لگانا مشکل تھا، چاہے گیٹس کیسے ترتیب دیئے گئے ہوں - مزید یہ کہ وہ فنکشن NP-مکمل جانا جاتا تھا۔ تمام محققین کو P بمقابلہ NP کو حل کرنے کے لیے کیا کرنا پڑا تھا Razborov کی تکنیک کو NOT گیٹس والے سرکٹس تک بڑھانا تھا۔

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

ریاستہائے متحدہ میں، روڈچ اسی سوال پر غور کر رہا تھا۔ وہ اور Impagliazzo کالج کے ہم جماعت تھے جو ایک ساتھ گریجویٹ اسکول گئے تھے۔ ان کی دوستی گوڈل اور ٹورنگ کے خود حوالہ ثبوتوں اور ریاضی اور کمپیوٹر سائنس کی بنیادوں پر ان کے مضمرات کے ساتھ مشترکہ دلچسپی سے پیدا ہوئی تھی۔

"ہمارا مذاق یہ تھا کہ ہم ایک بٹن حاصل کرنے جا رہے تھے جس میں کہا گیا تھا کہ 'خود کا حوالہ'،" امپاگلیزو نے کہا۔

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

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

اپنے طور پر دلچسپ ہونے کے باوجود، خفیہ نگاری خود حوالہ جاتی دلائل سے بہت دور دکھائی دیتی ہے جنہوں نے پہلے روڈیچ اور امپاگلیازو کو میدان میں کھینچا تھا۔ لیکن جیسا کہ روڈچ یہ سمجھنے کے لیے جدوجہد کر رہا تھا کہ سرکٹ کی پیچیدگی کا نقطہ نظر کیوں رک گیا ہے، اس نے یہ محسوس کرنا شروع کر دیا کہ دونوں مضامین ایک دوسرے سے بہت دور نہیں تھے۔ محققین نے P ≠ NP کو ثابت کرنے کی اپنی کوششوں میں جو حکمت عملی اپنائی تھی وہ Gödel کی مشہور تجویز "یہ بیان ناقابلِ ثابت ہے" کی یاد دلانے والا خود کو شکست دینے والا کردار تھا — اور خفیہ نگاری اس کی وضاحت کرنے میں مدد کر سکتی ہے۔ روس میں، رازبوروف نے اسی زمانے میں ایک ایسا ہی تعلق دریافت کیا۔ یہ قدرتی ثبوت رکاوٹ کے بیج تھے.

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

ایک ظالمانہ لطیفہ

1994 میں، Razborov اور Rudich نے محسوس کیا کہ انہوں نے اسی طرح کی بصیرتیں حاصل کی ہیں، اور انہوں نے اپنے نتائج کو یکجا کرنے کے لیے مل کر کام کرنا شروع کیا۔ انہوں نے پہلے مشاہدہ کیا کہ سرکٹ کی پیچیدگی کا استعمال کرتے ہوئے P ≠ NP کو ثابت کرنے کی تمام سابقہ ​​کوششوں نے ایک ہی عمومی حکمت عملی اپنائی تھی: NP-مکمل بولین فنکشن کی ایک خاص خاصیت کی شناخت کریں، پھر یہ ثابت کریں کہ کوئی بھی آسان حساب کرنے والا فنکشن ممکنہ طور پر اس پراپرٹی کو شیئر نہیں کر سکتا۔ یہ ظاہر کرے گا کہ منتخب کردہ NP-مکمل فنکشن کی گنتی کرنا واقعی مشکل تھا، P ≠ NP کو ثابت کرنا۔

Sipser، Razborov اور دوسروں نے اپنے زیادہ محدود نتائج کو ثابت کرنے کے لیے اسی حکمت عملی کو کامیابی کے ساتھ استعمال کیا تھا، اور ہر معاملے میں، محققین نے جس خاص خاصیت کی نشاندہی کی تھی وہ زیادہ تر بولین فنکشنز کے ذریعے شیئر کی گئی تھی۔ Razborov اور Rudich نے اس معاملے کا حوالہ دینے کے لیے "قدرتی ثبوت" کی اصطلاح وضع کی جہاں جائیداد کو وسیع پیمانے پر شیئر کیا گیا تھا، محض اس لیے کہ کوئی متبادل معلوم نہیں تھا۔ اگر "غیر فطری" ثبوت ممکن تھے، تو انہیں بہت متضاد اور نام کا مستحق ہونا پڑے گا۔

Razborov اور Rudich نے پھر اپنا بنیادی نتیجہ ثابت کیا: P ≠ NP کے قدرتی ثبوت کے لیے اس بات کی ایک بہت ہی جامع تفہیم کی ضرورت ہوگی کہ حساب کرنے میں آسان اور مشکل سے کام کرنے والے فنکشنز میں کس طرح فرق ہے، اور یہ علم آسانی سے تلاش کرنے کے لیے ایک تیز الگورتھم کو بھی فروغ دے سکتا ہے۔ فنکشنز کی گنتی کریں چاہے وہ سطحی طور پر پیچیدہ کیوں نہ ہوں۔ اگر پیچیدگی کے نظریہ دان P ≠ NP کے قدرتی ثبوت میں کامیاب ہو جاتے، تو انہوں نے صوابدیدی سچائی کی میز پر نظر ڈالنے اور اس بات کا تعین کرنے کے لیے کہ متعلقہ فنکشن میں زیادہ یا کم سرکٹ کی پیچیدگی ہے - ایک بہت زیادہ مضبوط اور عام نتیجہ تلاش کرنے کا تقریباً ایک ناقابل یقین طریقہ دریافت کر لیا ہوتا۔ وہ ثابت کرنے کے لیے نکلے تھے۔

کارموسینو نے کہا، "آپ تقریباً مدد نہیں کر سکتے لیکن اس سے زیادہ حاصل کر سکتے ہیں جس کے لیے آپ سودے بازی کرتے ہیں۔"

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

اس تعلق کو سمجھنے کے لیے، بہت سے ان پٹ متغیرات کے ساتھ بولین فنکشن کے سچ ٹیبل میں آؤٹ پٹ کالم کو دیکھنے اور ہر "سچ" کو 1 سے اور ہر "غلط" کو 0 سے تبدیل کرنے کا تصور کریں:

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

تو Razborov اور Rudich کے نتیجے سے ظاہر ہوا کہ P ≠ NP کا کوئی بھی قدرتی ثبوت بھی ایک تیز الگورتھم حاصل کرے گا جو چھپے ہوئے پیغامات پر مشتمل سیوڈورنڈم تاروں کو واقعی بے ترتیب پیغامات سے الگ کر سکتا ہے۔ محفوظ خفیہ نگاری ناممکن ہو گی — بالکل اس کے برعکس جو محققین نے P ≠ NP کو ثابت کر کے قائم کرنے کی امید کی تھی۔

دوسری طرف، اگر محفوظ خفیہ نگاری ممکن ہے، تو قدرتی ثبوت P ≠ NP کو ثابت کرنے کے لیے ایک قابل عمل حکمت عملی نہیں ہیں — محفوظ خفیہ نگاری کے لیے ایک شرط۔ مختصراً یہ قدرتی ثبوت کی رکاوٹ ہے۔ ایسا لگتا تھا جیسے پیچیدگی کے نظریہ ساز ایک ظالمانہ مذاق کے اختتام پر تھے۔

"اگر آپ سختی پر یقین رکھتے ہیں، تو آپ کو یقین کرنا چاہیے کہ سختی کو ثابت کرنا مشکل ہے،" کبنیٹس نے کہا۔

میٹاوورس میں۔

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

ولیمز نے کہا، "یہ وجدان ہے کہ 'اوہ، کیونکہ P ≠ NP، یہ ثابت کرنا مشکل ہے کہ P≠ NP،'" ولیمز نے کہا۔ "لیکن اس وجدان کو سمجھنے کے لیے، آپ کو P ≠ NP کو ایک کمپیوٹیشنل مسئلہ کے طور پر ثابت کرنے کے کام کے بارے میں سوچنا شروع کرنا ہوگا۔"

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

"میں کچھ اور تعلیمی کرنا چاہتا تھا،" کبنیٹس نے یاد کیا۔ "اور میں بھی دنیا کو دیکھنے کا متجسس تھا۔" وہ گریجویٹ اسکول کے لیے کینیڈا چلا گیا، اور وہیں اس نے قدرتی ثبوت کی رکاوٹ کے بارے میں سیکھا۔ کارموسینو کی طرح، Kabanets نتیجہ کے ساتھ مارا گیا تھا. "یہ بہت گہرا لگتا ہے کہ آپ کا یہ تعلق ہے،" انہوں نے کہا۔

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

Kabanets اور Cai کے مقالے نے Razborov اور Rudich کے قدرتی ثبوت کی رکاوٹ کی تشکیل میں مضمر ایک کمپیوٹیشنل مسئلہ پر روشنی ڈالی: بولین فنکشن کی سچائی جدول کو دیکھتے ہوئے، اس بات کا تعین کریں کہ آیا اس میں سرکٹ کی پیچیدگی زیادہ ہے یا کم۔ انہوں نے اسے کم از کم سرکٹ سائز کا مسئلہ، یا MCSP کہا۔

MCSP ایک اہم میٹا پیچیدگی کا مسئلہ ہے: ایک کمپیوٹیشنل مسئلہ جس کا موضوع گراف تھیوری یا کوئی اور خارجی موضوع نہیں ہے، بلکہ خود پیچیدگی تھیوری ہے۔ درحقیقت، یہ اس سوال کے ایک مقداری ورژن کی طرح ہے جس نے 1980 کی دہائی میں سرکٹ کی پیچیدگی کے نقطہ نظر کو استعمال کرتے ہوئے P بمقابلہ NP سے نمٹنے کے لیے پیچیدگی کے نظریہ سازوں کو راغب کیا: کون سے بولین فنکشنز کا حساب لگانا مشکل ہے، اور کون سے آسان؟

Impagliazzo نے کہا، "اگر ہم ایک MCSP الگورتھم کے ساتھ آتے ہیں، تو یہ خود کار طریقے سے ہوگا جیسا کہ ہم پیچیدگی تھیوری میں کیا کر رہے ہیں۔" "اس سے کم از کم ہمیں اپنے کام کو بہتر طریقے سے کرنے کے بارے میں ایک زبردست بصیرت ملنی چاہئے۔"

پیچیدگی کے نظریہ دان اس جادوئی الگورتھم کے بارے میں فکر نہیں کرتے ہیں کہ وہ کام سے باہر ہیں - وہ نہیں سوچتے کہ یہ بالکل موجود ہے، کیونکہ رازبوروف اور روڈچ نے دکھایا کہ اعلی پیچیدگی والے سچائی جدولوں کو کم پیچیدگی والے جدولوں سے ممتاز کرنے کے لیے ایسا کوئی الگورتھم خفیہ نگاری بنائے گا۔ ناممکن اس کا مطلب ہے کہ MCSP ممکنہ طور پر ایک مشکل کمپیوٹیشنل مسئلہ ہے۔ لیکن یہ کتنا مشکل ہے؟ کیا یہ NP-مکمل ہے، جیسے ہیملٹن کے راستے کا مسئلہ اور تقریباً ہر دوسرا مسئلہ جس کے ساتھ محققین نے 1960 کی دہائی میں جدوجہد کی؟

NP میں مسائل کے لیے، "یہ کتنا مشکل ہے؟" جواب دینے کے لیے عام طور پر کافی آسان ہوتا ہے، لیکن ایم سی ایس پی ایک عجیب وغریب معلوم ہوتا ہے۔ کبنیٹس نے کہا، "ہمارے پاس بہت کم 'تیرتے' مسائل ہیں جو NP-مکمل مسائل کے اس جزیرے سے منسلک نہیں ہیں، حالانکہ وہ مشکل معلوم ہوتے ہیں۔"

Kabanets جانتے تھے کہ وہ اور Cai اس مسئلے پر غور کرنے والے پہلے نہیں تھے جنہوں نے MCSP کو ڈب کیا تھا۔ سوویت ریاضی دانوں نے مختلف کمپیوٹیشنل مسائل کی اندرونی مشکل کو سمجھنے کی ابتدائی کوشش میں، 1950 کی دہائی میں شروع ہونے والے ایک بہت ہی ملتے جلتے مسئلے کا مطالعہ کیا تھا۔ لیونڈ لیون نے 1960 کی دہائی کے آخر میں NP-مکملیت کا نظریہ تیار کرنے کے دوران اس کے ساتھ کشتی لڑی تھی، لیکن وہ اسے NP-مکمل ثابت نہیں کر سکے، اور اس نے اس کے بغیر اپنا بنیادی مقالہ شائع کیا۔

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

"یہ ایک لحاظ سے، میٹا میٹا پیچیدگی ہے،" کہا راہل سنتھانم، آکسفورڈ یونیورسٹی میں ایک پیچیدگی تھیوریسٹ۔

لیکن کیا یہ سختی پوری طرح نیچے تھی، یا کم از کم یہ سمجھنے کا کوئی طریقہ تھا کہ محققین یہ ثابت کرنے میں کامیاب کیوں نہیں ہوئے کہ MCSP NP-مکمل تھا؟ Kabanets نے دریافت کیا کہ، ہاں، ایک وجہ تھی: سرکٹ کی پیچیدگی کو سمجھنے میں دشواری MCSP کی NP-مکملیت کو ثابت کرنے کے لیے کسی بھی معلوم حکمت عملی میں رکاوٹ کی طرح کام کرتی ہے - ایک ایسا مسئلہ جو خود سرکٹ کی پیچیدگی کو سمجھنے میں دشواری کے بارے میں ہے۔ قدرتی ثبوت کی رکاوٹ کی بٹی ہوئی، خود کو شکست دینے والی منطق ناگزیر لگ رہی تھی۔

یہ بھی ممکن ہے کہ MCSP NP-مکمل نہ ہو، لیکن اس کا بھی امکان نہیں لگتا ہے — مسئلے کی کچھ آسان قسمیں پہلے سے ہی NP-مکمل معلوم ہوتی ہیں۔

Impagliazzo نے کہا، "ہمارے پاس اسے ڈالنے کے لیے کوئی اچھی جگہ نہیں ہے جو اس کا براہ راست تعلق ان تمام دیگر مسائل سے ہے جن کا ہم مطالعہ کرتے ہیں۔"

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

العالمین کے جنگ

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

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

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

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

Impagliazzo نے کہا، "سوویت یونین میں ایک نوجوان محقق کے طور پر کامیاب ہونے کے لیے، آپ کو زیادہ رائے نہیں دی جا سکتی، اور یہ تصور کرنا مشکل ہے کہ لیونیڈ کی رائے نہیں،" Impagliazzo نے کہا۔

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

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

۔ کاغذ1995 میں شائع ہوا، ایک فوری کلاسک بن گیا۔ Impagliazzo کے لیے سنسنی خیز نام بنائے گئے۔ پانچ دنیا کمپیوٹیشنل سختی کی مختلف ڈگریوں اور مختلف کرپٹوگرافک صلاحیتوں سے ممتاز۔ ہم ان میں سے ایک دنیا میں رہتے ہیں، لیکن ہم نہیں جانتے کہ کون سا۔

جب سے Impagliazzo کا مقالہ سامنے آیا ہے، محققین نے اس کے چھوٹے سے ملٹیورس کے کچھ حصوں کو ختم کرنے کا خواب دیکھا ہے - یہ ثابت کر کے امکانات کی جگہ کو کم کرنا کہ کچھ دنیا آخر کار ممکن نہیں ہے۔ دو دنیا خاص طور پر پرکشش اہداف ہیں: وہ جہاں خفیہ نگاری ناممکن ہے اگرچہ P ≠ NP۔

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

یہ دونوں دنیایں میٹا پیچیدگی کے مسائل سے قریب سے جڑی ہوئی ہیں - خاص طور پر، Heuristica کی قسمت اس دیرینہ سوال سے منسلک ہے کہ آیا MCSP NP-مکمل ہے۔ وہ سوال جس نے کبنیٹس کو متوجہ کیا اور لیون کو بہت پہلے اسٹمپ کیا وہ محض تجسس نہیں ہے: پوری دنیا داؤ پر لگی ہوئی ہے۔

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

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

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

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

کارموسینو نے کہا ، "میں اس وقت اس کاغذ کا جنون تھا۔ ’’کچھ بھی نہیں بدلا۔‘‘

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

"وہ لوگوں کو اچھے طریقے سے بگاڑ رہا تھا،" کبنیٹس نے یاد کیا۔

سب سے پہلے، کارموسینو کے پاس MCSP کے ورژن کے لیے NP-مکملیت کو ثابت کرنے کے لیے نئے آئیڈیاز تھے جو قدرتی ثبوت کی رکاوٹ پر Razborov اور Rudich کے مقالے میں شائع ہوئے تھے۔ لیکن ان خیالات کا اظہار نہیں ہوا۔ اس کے بجائے، Impagliazzo کے ایک آف دی کف ریمارک نے چاروں محققین کو یہ احساس دلایا کہ قدرتی ثبوتوں کی رکاوٹ اس سے زیادہ طاقتور الگورتھم پیدا کر سکتی ہے جتنا کسی نے محسوس نہیں کیا تھا - روڈ بلاک میں ایک خفیہ نقشہ موجود تھا۔

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

Impagliazzo نے کہا کہ "یہ واضح نہیں تھا کہ اس طرح کا تعلق بالکل موجود ہو گا۔"

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

لیکن MCSP کے کچھ آسان ورژنز کے لیے — جب سرکٹس پر مخصوص پابندیاں ہوں تو اعلی پیچیدگی والے سچائی جدولوں کو کم پیچیدگی والے جدولوں سے ممتاز کرنا — تیز الگورتھم کئی سالوں سے مشہور ہیں۔ Carmosino, Impagliazzo, Kabanets اور Kolokolova کے مقالے سے پتہ چلتا ہے کہ ان الگورتھم کو سیکھنے کے الگورتھم میں تبدیل کیا جا سکتا ہے جو کہ اسی طرح محدود تھے لیکن پھر بھی اس سے کہیں زیادہ طاقتور ہیں جسے محققین نے پہلے اتنی سخت نظریاتی سطح پر سمجھا تھا۔

Ilango نے کہا، "کسی نہ کسی طرح ان کا خود حوالہ ذائقہ آپ کو وہ کام کرنے کے قابل بناتا ہے جو بظاہر آپ زیادہ معیاری مسائل کے ساتھ نہیں کر سکتے۔"

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

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

Impagliazzo نے کہا، "اس قسم کی دوہرییت کم از کم پچھلے 30 یا 40 سالوں کی پیچیدگی میں ایک تھیم ہے۔" "رکاوٹیں اکثر مواقع ہوتی ہیں۔"

جزوی کریڈٹ

کارموسینو اور اس کے ساتھیوں نے اپنا مقالہ شائع کرنے کے بعد سے سالوں میں ہی ترقی میں تیزی آئی ہے۔

"نئی چیزیں ہو رہی ہیں،" کولوکولوا نے کہا۔ "واقعی بہت سارے، واقعی روشن جونیئر محققین ہیں۔"

Ilango ان نوجوان محققین میں سے ایک ہے - گریجویٹ اسکول کے اپنے پہلے تین سالوں میں، اس نے دو جہتی حکمت عملی کا استعمال کرتے ہوئے MCSP NP-مکمل ثابت کرنے کے مشکل کھلے مسئلے پر حملہ کیا: NP کی تکمیل کو ثابت کرنا سادہ ورژن MCSP کا، جیسا کہ سرکٹ کی پیچیدگی کے محققین نے 1980 کی دہائی میں P بمقابلہ NP پر حملہ کرتے ہوئے کیا تھا، جبکہ NP کی تکمیل کو بھی ثابت کیا تھا۔ زیادہ پیچیدہ ورژن، جو بدیہی طور پر مشکل معلوم ہوتا ہے اور اس طرح مشکل ثابت کرنا شاید آسان ہوتا ہے۔

Ilango میٹا پیچیدگی میں اپنی دلچسپی کا سہرا دیتا ہے۔ ایرک ایلینڈر، Rutgers یونیورسٹی میں ایک پیچیدگی تھیوریسٹ اور ان چند محققین میں سے ایک جنہوں نے 2000 اور 2010 کی دہائی کے اوائل میں میٹا پیچیدگی پر کام جاری رکھا۔ "اس کا جوش متعدی تھا،" الانگو نے کہا۔

ایلینڈر سے متاثر ایک اور نوجوان محقق ہے۔ شوچی ہیرہارااب ٹوکیو میں نیشنل انسٹی ٹیوٹ آف انفارمیٹکس میں پروفیسر ہیں۔ 2018 میں گریجویٹ طالب علم ہونے کے دوران ہیرہارا نے میٹا پیچیدگی اور اوسط کیس کی پیچیدگی کے درمیان تعلق کی حقیقی حد کا انکشاف کیا جسے کارموسینو اور اس کے شریک مصنفین نے دریافت کیا تھا۔ ان چار محققین نے ایک مسئلے کی اوسط کیس کی پیچیدگی — MCSP — اور دوسرے کی بدترین کیس کی پیچیدگی — بولین لرننگ کے درمیان تعلق پایا تھا۔ ہیرہارا نے اپنی تکنیک کو مزید ترقی دی۔ اخذ کردہ MCSP کے لیے بدترین کیس سے اوسط کیس میں کمی۔ اس کا نتیجہ یہ ظاہر کرتا ہے کہ ایک فرضی اوسط کیس MCSP الگورتھم جیسا کہ Carmosino اور اس کے ساتھیوں نے غور کیا تھا کہ وہ MCSP کے قدرے مختلف ورژن کو بغیر کسی غلطی کے حل کرنے کے لیے کافی طاقتور ہوگا۔

ہیرہارا کا نتیجہ دلچسپ ہے کیونکہ بہت سے محققین کو شبہ ہے کہ MCSP NP-مکمل ہے، دوسرے تمام مسائل کے برعکس جن کے لیے بدترین کیس سے اوسط کیس میں کمی معلوم ہوتی ہے۔ اگر وہ تمام اوسط کیس الگورتھم کا احاطہ کرنے کے لیے Hirahara کے نتائج کو بڑھا سکتے ہیں اور پھر یہ ثابت کر سکتے ہیں کہ MCSP NP-مکمل ہے، تو یہ ثابت کرے گا کہ ہم Heuristica میں نہیں رہتے۔

"یہ واقعی زمین کو ہلا دینے والا نتیجہ ہوگا،" سنتھانم نے کہا۔

یہ ثابت کرنا کہ MCSP NP-مکمل ہے ایک لمبے آرڈر کی طرح لگتا ہے - آخر کار، یہ سوال 50 سالوں سے کھلا ہے۔ لیکن ایک کے بعد پیش رفت گزشتہ سال ہیراہارا کے ذریعہ، محققین اب اس سے کہیں زیادہ قریب ہیں جس کی توقع کچھ سال پہلے کسی نے کی ہوگی۔

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

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

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

"یہ حیرت انگیز کام ہے،" ولیمز نے کہا۔ "ہر ایک نے سوچا کہ یہ جزوی مسائل تقریباً وہی مشکل ہیں جو مکمل مسئلہ ہیں۔"

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

گم شدہ ٹکڑے

MCSP بھی واحد میٹا پیچیدگی کا مسئلہ نہیں ہے جس نے ایک اہم پیش رفت کی حوصلہ افزائی کی ہے۔ 2020 میں، Cornell Tech cryptographer رافیل پاس۔ اور اس کا گریجویٹ طالب علم یانی لیو ایک کنکشن دریافت کیا ایک مختلف میٹا پیچیدگی کے مسئلے اور ایک بنیادی کرپٹوگرافک پروٹوکول کے درمیان جو Heuristica اور Pessiland کے درمیان حد کی وضاحت کرتا ہے، Impagliazzo کی بدترین دنیا (جہاں NP-مکمل مسائل اوسط کیس کے لحاظ سے مشکل ہیں لیکن خفیہ نگاری اب بھی ناممکن ہے)۔ اس سے مسئلہ پیدا ہوتا ہے کہ انہوں نے پیسی لینڈ پر حملے کے لیے ایک اہم امیدوار کا مطالعہ کیا، اور ان کے زیادہ حالیہ کام اشارہ کرتا ہے کہ یہ Heuristica کے خلاف بھی کام کر سکتا ہے۔

"پزل کے مختلف ٹکڑے غائب ہیں،" پاس نے کہا۔ "میرے لیے یہ صرف جادوئی ہے کہ یہ فیلڈز اتنے گہرے طور پر جڑے ہوئے ہیں۔"

ہیرہارا نے خبردار کیا ہے کہ چیلنجز ابھی بھی محققین کا انتظار کر رہے ہیں جو 30 سال پہلے امپاگلیازو کی دنیا کو ختم کرنے کے ارادے سے ہیں۔ "میں یہ کہنا چاہوں گا کہ کسی وقت Heuristica اور Pessiland کو مسترد کر دیا جائے گا، لیکن مجھے یقین نہیں ہے کہ ہم کتنے قریب ہیں،" انہوں نے کہا۔

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

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

اگر محققین نے P بمقابلہ NP سوال کا جواب دینے کے لیے اپنی جدوجہد سے ایک سبق سیکھا ہے — یا یہاں تک کہ اسے صرف سمجھ لیا ہے — تو یہ ہے کہ پیچیدگی کا نظریہ خود پیچیدہ ہے۔ لیکن یہ چیلنج بالکل وہی ہے جو جدوجہد کو اتنا فائدہ مند بناتا ہے۔

کارموسینو نے کہا کہ "یہ واقعی بہت اچھا ہے کہ یہ بہت مشکل ہے۔" "میں کبھی بور نہیں ہونے والا ہوں۔"

ایڈیٹر کا نوٹ: سکاٹ ایرونسن کا ممبر ہے۔ کوتاٹا میگزینکی ایڈوائزری بورڈ.