وہ محقق جو نئی دنیاؤں کو جوڑ کر کمپیوٹیشن کو دریافت کرتا ہے۔ کوانٹا میگزین

تصور کریں کہ آپ حساب کی نوعیت کو سمجھنے کی جستجو میں ہیں۔ آپ کسی بھی راستوں سے بہت دور بیابان میں ہیں، اور ناقابل تسخیر پیغامات آپ کے چاروں طرف درختوں کے تنوں میں تراشے گئے ہیں — BPP, AC⁰[m]، Σ₂P، YACC، اور سینکڑوں دیگر۔ گلف آپ کو کچھ بتانے کی کوشش کر رہے ہیں، لیکن کہاں سے شروع کریں؟ آپ ان سب کو سیدھا بھی نہیں رکھ سکتے۔

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

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

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

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

Quanta مشکل مسائل اور مشکل پہیلیاں، کنسلٹنگ اوریکلز اور امپروو کامیڈی کے ریاضی کے اسباق کے بارے میں Impagliazzo کے ساتھ بات کی۔ انٹرویو کو کم کیا گیا ہے اور وضاحت کے لیے اس میں ترمیم کی گئی ہے۔

آپ کو پہلی بار ریاضی میں دلچسپی کب آئی؟

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

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

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

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

آپ کا کچھ مشہور کام کرپٹوگرافی اور کمپیوٹیشنل پیچیدگی تھیوری کے درمیان تعلق کو دریافت کرتا ہے۔ ان دونوں شعبوں کا تعلق کیوں ہے؟

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

ایک مسئلہ اور ایک پہیلی میں کیا فرق ہے؟

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

پانچ جہانوں کے درمیان فرق یہ ہے کہ وہ سوالوں کا جواب کیسے دیتے ہیں "کیا کوئی مشکل مسائل ہیں؟" اور "کیا مشکل پہیلیاں ہیں؟"

وہ مختلف جوابات کیسے چلتے ہیں؟

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

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

آپ کو فائیو ورلڈ پیپر لکھنے کے لیے کس چیز نے ترغیب دی؟

اس وقت، یہ معلوم تھا کہ P بمقابلہ NP سوال کے مختلف جوابات اس بات پر بڑا اثر ڈالیں گے کہ ہم کس قسم کے مسائل کو حل کر سکتے ہیں اور یہ بھی کہ ہم کس قسم کی سلامتی کی امید کر سکتے ہیں، لیکن آسانی کی مختلف شکلوں کے درمیان معیار کے فرق اور سختی واقعی واضح نہیں تھی.

ابھی چند سال پہلے ایک بہت ہی بصیرت والا مقالہ تھا جس میں 20 ممکنہ جوابات کے ساتھ بہت سے باہمی تعلق والے سوالات کا استعمال کرتے ہوئے امتیازات بیان کیے گئے تھے۔ پانچ دنیا کا مقالہ لکھنے کی ایک وجہ یہ تھی کہ ہم نے ان چند سالوں میں بہت زیادہ ترقی کی تھی۔ 20 ممکنہ دنیاوں کے نام تلاش کرنا مشکل ہوتا۔

تو اس طرح کیوں فریم کریں، نرالا ناموں کے ساتھ مختلف دنیاؤں کی طرح؟

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

کیا محققین نے پانچ ممکنہ دنیاوں میں سے کسی کو مسترد کر دیا ہے؟

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

فرضی دنیا بھی پیچیدگی تھیوری میں ایک اور کردار ادا کرتی ہے، ایسے ثبوتوں میں جو "اوریکلز" کے وجود کو مانتے ہیں۔ تو، سب سے پہلے، اصل میں ایک اوریکل کیا ہے؟

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

کیا محققین کا خیال ہے کہ یہ جادوئی خانے حقیقت میں موجود ہوسکتے ہیں؟

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

آپ نے کمپیوٹیشنل سختی اور بے ترتیب پن کے درمیان روابط بھی دریافت کیے ہیں۔ وہ کنکشن کیسے کام کرتا ہے؟

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

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

لہذا بصیرت یہ ہے کہ وہ مشکل مسائل جن کے حل کے بارے میں ہم نہیں جانتے ہیں وہ "سیڈورینڈم" نمبروں کا ذریعہ فراہم کرسکتے ہیں جو بے ترتیب نظر آتے ہیں۔

Monty Python کے بارے میں بات کرتے ہوئے، میں جانتا ہوں کہ آپ کافی عرصے سے امپروو کامیڈی کر رہے ہیں — آپ کی شروعات کیسے ہوئی؟

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

وہ کیا سوچتی تھی؟

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

میری اب کی بیوی نے کلاس سے وقفہ لیا، اور جب وہ ایک سال بعد واپس آئی تو میں اسے متاثر کرنے میں کامیاب رہا۔ یہ 30 سال پہلے تھا۔ میں اب بھی ایک ہی انسٹرکٹر کے ساتھ ایک ہی کلاس لیتا ہوں۔

کیا بہتری نے آپ کی تحقیق تک پہنچنے کا طریقہ بدل دیا ہے؟

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

کیا پسند ہے؟

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

رول پلےنگ گیمز سے آپ کی محبت کا کیا ہوگا - کیا اس نے آپ کے کام کو بالکل متاثر کیا ہے؟

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

کردار ادا کرنے والے گیمز فرضی دنیا کو دریافت کرنے کا ایسا زبردست طریقہ کیوں ہیں؟

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