محققی که محاسبات را با ایجاد دنیای جدید کشف می کند | مجله کوانتا

تصور کنید که در تلاش برای درک ماهیت محاسبات هستید. تو در اعماق بیابان، دور از هر مسیری، و غیر قابل درک پیام در تنه درختان در اطراف شما حک شده اند - BPP، AC⁰[m]، Σ₂P، YACC، و صدها مورد دیگر. گلیف ها سعی می کنند چیزی به شما بگویند، اما از کجا باید شروع کرد؟ شما حتی نمی توانید همه آنها را صاف نگه دارید.

تعداد کمی از محققین به این اندازه انجام داده اند راسل ایمپاگلیازو برای عبور از این هرج و مرج ظاهری. به مدت 40 سال، ایمپاگلیازو در خط مقدم نظریه پیچیدگی محاسباتی، مطالعه دشواری ذاتی مسائل مختلف کار کرده است. معروف‌ترین سوال باز در این زمینه، به نام مسئله P در مقابل NP، می‌پرسد آیا بسیاری از مسائل محاسباتی به ظاهر سخت واقعاً آسان هستند - با الگوریتم مناسب. یک پاسخ پیامدهای گسترده ای برای علم و امنیت رمزنگاری مدرن خواهد داشت.

در دهه‌های 1980 و 1990، ایمپاگلیازو نقش اصلی را در اتحاد مبانی نظری رمزنگاری. در سال 1995، او اهمیت این پیشرفت‌های جدید را در مقاله‌ای نمادین بیان کرد که راه‌حل‌های ممکن برای P در مقابل NP و تعداد انگشت شماری از مشکلات مرتبط را به زبان پنج جهان فرضی ما ممکن است ساکن باشیم که به طرز عجیبی Algorithmica، Heuristica، Pessiland، Minicrypt و Cryptomania نامیده می شوند. پنج جهان Impagliazzo الهام بخش نسلی از محققان بوده است و آنها همچنان به هدایت تحقیقات در زیر زمینه شکوفایی می پردازند. فراپیچیدگی.

و این تنها دنیاهایی نیستند که او در رویاهایش دیده است. Impagliazzo مادام العمر از علاقه مندان به بازی های نقش آفرینی رومیزی مانند Dungeons و Dragons بوده است و از اختراع آن لذت می برد. مجموعه قوانین جدید و تنظیمات جدید برای کاوش همین روحیه بازیگوش، تمرین 30 ساله کمدی بداهه او را متحرک می کند.

ایمپاگلیازو همچنین کار اساسی برای روشن کردن نقش اساسی تصادفی در محاسبات انجام داد. در اواخر دهه 1970، دانشمندان کامپیوتر دریافتند که تصادفی بودن گاهی اوقات ممکن است بهبود الگوریتم ها برای حل مسائل ذاتا قطعی - یافته ای غیرقابل درک که سال ها محققان را گیج می کرد. کار ایمپاگلیازو با نظریه پرداز پیچیدگی آوی ویگدرسون و سایر محققان در دهه 1990 نشان دادند که اگر برخی مسائل محاسباتی واقعاً اساساً سخت باشند، پس همیشه ممکن است برای تبدیل الگوریتم هایی که از تصادفی بودن استفاده می کنند به الگوریتم های قطعی. و برعکس، اثبات اینکه تصادفی بودن را می توان از هر الگوریتمی حذف کرد نیز ثابت خواهد کرد که مشکلات واقعا سخت وجود دارد.

کوانتوم با ایمپاگلیازو در مورد تفاوت بین مسائل سخت و پازل های سخت، مشاوره با اوراکل ها و درس های ریاضی کمدی بداهه صحبت کرد. مصاحبه برای وضوح فشرده و ویرایش شده است.

اولین بار چه زمانی به ریاضیات علاقه مند شدید؟

من حتی قبل از اینکه واقعاً بفهمم چیست به ریاضی علاقه مند بودم. در کلاس سوم، نمرات ریاضی من شروع به لغزش کرد، زیرا قرار بود جدول ضرب خود را حفظ کنیم و من نپذیرفتم. مادرم گفت: "اما راسل، تو عاشق ریاضی هستی، چرا این کار را نمی کنی؟" و من گفتم: «این ریاضی نیست، حفظ کردن است. ریاضی واقعی مستلزم حفظ کردن نیست.» تنها چیزی که در آن مرحله آموخته بودم حساب بود، بنابراین مطمئن نیستم که این مفهوم را که ریاضی درباره مفاهیم انتزاعی است از کجا آوردم.

در مورد علوم کامپیوتر چطور؟ بخش‌هایی از این رشته بسیار انتزاعی هستند، اما آن چیزی نیست که بیشتر مردم در ابتدا با آن مواجه می‌شوند.

در دبیرستان، یک دوره برنامه نویسی در بیسیک داشتم، اما انجام کاری واقعاً سخت بود. برنامه ها باید به نوارهای کاغذی منتقل می شدند، که باید از طریق این رایانه بسیار قدیمی اجرا می شد که اغلب خراب می شد و کاغذ شما را از وسط می برد. بنابراین من فکر می کردم که علوم کامپیوتر به طرز وحشتناکی کسل کننده است.

من قصد داشتم منطق بخوانم. اما بسیاری از مفاهیم، ​​زمانی که سعی می‌کردید آنها را رسمی کنید، شامل محاسبات و به‌ویژه محدودیت‌هایی در محاسبه بودند. سوالاتی مانند "چگونه می دانیم که چیزهایی در ریاضیات درست هستند؟" و "چگونه دشواری انجام ریاضیات را درک کنیم؟" به علوم کامپیوتر نظری و به ویژه نظریه پیچیدگی منجر شد.

برخی از معروف ترین کارهای شما به بررسی ارتباط بین رمزنگاری و نظریه پیچیدگی محاسباتی می پردازد. چرا این دو رشته به هم مرتبط هستند؟

هنگامی که در حال راه اندازی یک سیستم رمزنگاری هستید، باید بین کاربران قانونی - افرادی که می خواهید به آنها اجازه دسترسی بدهید - و همه افراد دیگر تمایز قائل شوید. مشکلات محاسباتی دشوار راهی به ما می دهد تا این گروه ها را بر اساس دانسته هایشان تشخیص دهیم. اما اگر می‌خواهید پاسخ یک مسئله را راهی برای تشخیص دو گروه از افراد بدانید، نمی‌توانید فقط از هر مشکل سختی استفاده کنید - به یک پازل سخت نیاز دارید.

تفاوت بین یک مشکل و یک پازل چیست؟

به طور کلی، شخصی که مشکلی را مطرح می کند ممکن است پاسخ را نداند. پازل مسئله ای است که با یک پاسخ در ذهن طراحی شده است. پس چرا به یک پازل نیاز داریم؟ زیرا ما باید بتوانیم تعیین کنیم که آیا فردی که ظاهراً آن را حل کرده است، واقعاً این کار را انجام داده است یا خیر. در زندگی روزمره، ما از پازل ها برای سرگرمی استفاده می کنیم، اما همچنین از آنها در کلاس های درس استفاده می کنیم تا بررسی کنیم که آیا مردم مطالب را می فهمند یا خیر. این چیزی است که در رمزنگاری اتفاق می‌افتد: ما از پازل‌ها برای آزمایش دانش دیگران استفاده می‌کنیم.

تفاوت بین پنج جهان در نحوه پاسخگویی آنها به سؤالات "آیا مشکلات سخت وجود دارد؟" است. و "آیا پازل های سخت وجود دارد؟"

چگونه آن پاسخ های مختلف بازی می کنند؟

در جهان اول، الگوریتمیکا، هیچ مشکلی سخت نیست. لازم نیست بدانید کسی مشکل شما را چگونه طراحی کرده است: همیشه می توانید آن را حل کنید. Heuristica می‌گوید، "خب، شاید چند مشکل سخت باشند." سپس به Pessiland می رسیم، جایی که بسیاری از مشکلات سخت هستند، اما بیشتر پازل ها اینطور نیستند. تقریباً هر مشکلی را که من در جایی که راه حل آن را بدانم مطرح کنم، شما نیز قادر خواهید بود آن را حل کنید. همه این دنیاها برای رمزنگاری بد هستند.

در Minicrypt، من می‌توانم پازل‌هایی ایجاد کنم که می‌دانم چگونه آن‌ها را حل کنم که هنوز برای شما واقعاً چالش برانگیز هستند. و در نهایت، کریپتومانیا دنیایی است که در آن دو نفر می توانند در یک مکان عمومی بایستند که در آن یک استراق سمع می تواند بشنود و با هم پازلی را ایجاد کنند که هنوز برای استراق سمع کننده سخت است.

انگیزه شما برای نوشتن مقاله پنج جهان چیست؟

در آن زمان، مشخص بود که پاسخ‌های متفاوت به سؤال P در مقابل NP تأثیر زیادی بر روی اینکه چه نوع مشکلاتی را می‌توانیم حل کنیم و همچنین به چه نوع امنیت می‌توانیم امیدوار باشیم، خواهد داشت، اما تمایزات کیفی بین اشکال مختلف سهولت و سهولت سختی واقعا واضح نبود

فقط چند سال قبل مقاله بسیار روشنگری وجود داشت که تمایزات را با استفاده از بسیاری از سوالات مرتبط با 20 پاسخ ممکن بیان می کرد. یکی از دلایلی که می خواستم مقاله پنج جهان را بنویسم این بود که در آن چند سال پیشرفت زیادی کرده بودیم. پیدا کردن نام برای 20 دنیای ممکن دشوار بود.

پس چرا آن را به این شکل، به عنوان جهان های مختلف با نام های عجیب و غریب قاب بندی کنید؟

من موافقت کرده بودم که این مقاله را برای یک کنفرانس بنویسم. شب‌ها تا دیروقت بیدار می‌ماندم و سعی می‌کردم بفهمم چه می‌خواهم بگویم، و حدود ساعت ۱ بامداد، قاب‌بندی دنیاهای مختلف ایده خوبی به نظر می‌رسید. و سپس صبح روز بعد آن را خواندم و هنوز ایده خوبی به نظر می رسید - این راهی بود برای نشان دادن اینکه چگونه این ایده ها واقعاً بر جهان تأثیر می گذارند بدون اینکه گرفتار جزئیات کمی شوند. چیزی که من را در مورد این مقاله خوشحال می کند این است که از افرادی که در تحقیقات پیچیده انجام می دهند می شنوم که این مقاله ای بود که آنها را در مقطع کارشناسی به این رشته علاقه مند کرد.

آیا محققان هیچ یک از پنج جهان ممکن را رد کرده اند؟

ما در واقع موارد بیشتری را اضافه می کنیم - مردم شروع به صحبت در مورد آن کرده اند آبفوستوپیا به عنوان دنیایی از ابزارهای رمزنگاری قوی تر. این که ما در اواخر دهه 1980 این همه پیشرفت کردیم و از آن زمان تاکنون هیچ جهانی را حذف نکرده ایم، کمی ناامید کننده است. اما از طرف دیگر، ما چیزهای بیشتری در مورد ارتباطات بین دنیاها می دانیم و یک تصویر بسیار واضح تر از اینکه هر دنیا چه شکلی خواهد بود

جهان‌های فرضی نیز نقش دیگری در نظریه پیچیدگی دارند، در اثبات‌هایی که وجود «اوراکل‌ها» را فرض می‌کنند. بنابراین، اول از همه، اوراکل دقیقا چیست؟

تصور کنید شخصی دستگاهی مبتکرانه بسازد که می تواند مشکلی را حل کند بدون اینکه ما الگوریتمی برای حل آن مشکل بدانیم. اوراکل یعنی همین. اگر ما چنین دستگاه معجزه‌آسایی داشتیم و آن را در رایانه‌هایمان قرار می‌دادیم، می‌توانست خط بین آنچه قابل محاسبه و غیرقابل محاسبه است تغییر کند.

آیا محققان فکر می کنند که این جعبه های جادویی می توانند واقعا وجود داشته باشند؟

نه، احتمالا وجود ندارند. در اوایل، نتایج اوراکل تا حدودی بحث برانگیز بود، زیرا آنها بسیار فرضی هستند. اما یکی از راه هایی که می توانند بسیار روشنگر باشند، زمانی است که از اوراکل برای مدل سازی یک موقعیت ایده آل استفاده می شود. فرض کنید که می‌خواهید نشان دهید که A لزوماً به معنای B نیست. شما با تنظیماتی شروع می‌کنید که در آن افراطی‌ترین A را دارید و نشان می‌دهید که هنوز برای تضمین B کافی نیست. اگر می‌توانید نشان دهید که حتی اگر همه شانس‌ها وجود داشته باشد به نفع شما هنوز نمی توانید چیزی را ثابت کنید، این واقعاً شواهد قوی است که اثبات آن دشوار خواهد بود.

شما همچنین ارتباط بین سختی محاسباتی و تصادفی را کشف کرده اید. آن اتصال چگونه کار می کند؟

این واقعاً راهی است برای گفتن اینکه اگر چیزی را متوجه نشدید، ممکن است تصادفی به نظر برسد. فرض کنید من می گویم به عددی بین یک تا هزار فکر می کنم. اگر عدد را به صورت تصادفی انتخاب کنم، شما یک در هزار شانس حدس زدن آن را دارید. و اگر بپرسم - به دنبال مونتی پایتون - "در مایل در ساعت، میانگین سرعت هوایی یک پرستو اروپایی چقدر است؟" شما تقریباً همین شانس را دارید احتمالاً بیش از یک مایل در ساعت می‌رود و احتمالاً بیش از هزار مایل در ساعت نمی‌رود.

این در واقع تصادفی نیست - این یک سوال قطعی قابل پاسخ است. ما فقط می‌توانیم همه پرستوهایی را که در اطراف پرواز می‌کنند اندازه‌گیری کنیم، اما تعیین آن با منابع محدود، مانند نداشتن بودجه برای اندازه‌گیری سرعت بلع و نداشتن ذخایر بی‌نهایت پرستو، سخت است.

بنابراین بینش این است که مسائل سختی که راه‌حل‌های آنها را نمی‌دانیم می‌توانند منبعی از اعداد «شبه‌تصادفی» باشند که تصادفی به نظر می‌رسند.

وقتی صحبت از مونتی پایتون شد، می‌دانم که شما مدت‌هاست که کمدی بداهه کار می‌کنید - چگونه شروع کردید؟

من در سال 1991 به عنوان استادیار در سن دیگو شروع کردم. و در حدود سال 94 یا بیشتر، فکر کردم، "من واقعاً زندگی زیادی در خارج از دپارتمان ندارم." بنابراین من هفته نامه رایگان دریافت کردم و لیست باشگاه ها و فعالیت ها را بررسی کردم. من همه چیز را حذف کردم به جز کمدی بداهه - فکر می کردم حداقل قابل قبول است که در آن خوب باشم. من در آن کلاس مبتدی با همسرم آشنا شدم.

او چه فکر می کرد؟

او می گوید من واقعا افتضاح بودم. وقتی یک منطق‌دان هستید، آموزش دیده‌اید که همیشه به نکات ظریف هر کلمه فکر کنید. شما نمی خواهید چیزی نادرست بگویید. Improv از این جهت عالی است که این را معکوس می‌کند: هدف این نیست که چیزی کامل بگوییم، بلکه چیزی را سریع بسازیم. برعکس بقیه عمرم بود.

همسر کنونی من از کلاس استراحت کرد و وقتی یک سال بعد برگشت، توانستم او را تحت تاثیر قرار دهم. این 30 سال پیش بود. من هنوز در همان کلاس با همان مربی شرکت می کنم.

آیا انجام پیشرفت در رویکرد شما به تحقیقاتتان تغییر کرده است؟

این تمرین خوبی است که در مورد هر فکری که دارید بیش از حد انتقاد نکنید. این به ویژه در همکاری ها مفید است. زمانی که با افراد دیگر کار می‌کردم، جملاتی از این قبیل می‌گفتم: «اما این ایده به دلایل زیر جواب نمی‌دهد. این به معنای واقعی کلمه درست نیست.» در بداهه سازی، شما همیشه باید آنچه را که شریکتان می گوید بپذیرید. و من فکر می‌کنم این نگرش خوبی است، به‌ویژه زمانی که در حال تحقیق با دانش‌آموزان هستید: چیزی را که آنها می‌گویند صرفاً به این دلیل که می‌دانید نادرست است رد نکنید. ایده های خوب زیادی وجود دارد که 100% درست نیستند.

مانند آنچه که؟

وقتی می‌خواهید برای مشکلی شهود به دست آورید، چیزی که کمک می‌کند این است که با برخی فرضیات ساده‌کننده شروع کنید. این مفروضات معمولاً درست نیستند، اما می توانند به شما کمک کنند تا یک نقشه راه تهیه کنید. بگو: "اگر یک فیل داشتم، می توانستم از کوه ها عبور کنم. البته من فیل ندارم. اما اگر این کار را انجام می‌دادم، این کار به این صورت است.» و سپس متوجه می شوید، "خب، شاید من برای این مرحله به فیل نیاز نداشته باشم. یک قاطر خوب می شود.»

در مورد عشق شما به بازی های نقش آفرینی چطور - آیا این اصلاً روی کار شما تأثیر گذاشته است؟

ممکن است بر تمام تحقیقات من تأثیری نداشته باشد، اما مطمئناً بر مقاله پنج جهان من تأثیر گذاشته است. من همیشه علاقه کلی به فانتزی و علمی تخیلی و ارائه دنیاهای ممکن مختلف داشته ام - اگر همه چیز متفاوت بود، اوضاع چگونه خواهد بود؟

چرا بازی های نقش آفرینی چنین روشی قانع کننده برای کشف جهان های فرضی هستند؟

افرادی که اهل داستان های تخیلی هستند همیشه دنیاها را اختراع کرده اند. تالکین بیشتر به خاطر آن مشهور است، و چنان تخیل عظیمی داشت که در واقع احساس می‌کرد دنیایش در آن زندگی می‌کند. راهی برای انجام آن است. حالا فقط دنیای من نیست. ممکن است همانطور که من تصور می‌کردم شروع شده باشد، اما درست مانند هر همکاری، به دلیل مشارکت‌های دیگران، از آن گذشته است.