تخيل أنك تسعى إلى فهم طبيعة الحساب ذاتها. أنت في أعماق البرية، بعيدًا عن كل الطرق، و غامض رسائل محفورة في جذوع الأشجار من حولك - BPP، AC⁰[م]، Σ₂P، YACC، ومئات آخرين. تحاول الحروف الرسومية أن تخبرك بشيء ما، ولكن من أين تبدأ؟ لا يمكنك حتى الاحتفاظ بها جميعًا بشكل مستقيم.

قليل من الباحثين فعلوا مثل هذا راسل إمباجلياتسو لقطع هذه الفوضى الظاهرة. لمدة 40 عامًا، عمل إمباليازو في طليعة نظرية التعقيد الحسابي، وهي دراسة الصعوبة الجوهرية للمشكلات المختلفة. السؤال المفتوح الأكثر شهرة في هذا المجال، والذي يسمى مشكلة P مقابل NP، يسأل ما إذا كانت العديد من المشاكل الحسابية التي تبدو صعبة هي في الواقع سهلة - باستخدام الخوارزمية الصحيحة. سيكون للإجابة آثار بعيدة المدى على العلوم وأمن التشفير الحديث.

في الثمانينيات والتسعينيات، لعب إمباليازو دورًا رائدًا في توحيد البلاد. الأسس النظرية للتشفير. في عام 1995، أوضح أهمية هذه التطورات الجديدة في ورقة بحثية مبدعة أعادت صياغة الحلول الممكنة لـ P مقابل NP وحفنة من المشاكل ذات الصلة بلغة خمسة عوالم افتراضية قد نسكن في ما يُطلق عليه اسم Algorithmica، وHeuristica، وPessiland، وMinicrypt، وCryptomania. لقد ألهمت عوالم إمباجلياتسو الخمسة جيلًا من الباحثين، وما زالوا مستمرين في توجيه الأبحاث في المجال الفرعي المزدهر وهو علم النفس. التعقيد الفوقي.

وهذه ليست العوالم الوحيدة التي حلم بها. لقد كان Impagliazzo من عشاق ألعاب لعب الأدوار على الطاولة طوال حياته مثل Dungeons وDragons، ويسعده ابتكار مجموعات جديدة من القواعد وإعدادات جديدة للاستكشاف. نفس الروح المرحة تنعش ممارسته للكوميديا ​​الارتجالية لمدة 30 عامًا.

قام Impagliazzo أيضًا بعمل تأسيسي لتوضيح الدور الأساسي للعشوائية في الحساب. في أواخر السبعينيات، اكتشف علماء الكمبيوتر أن العشوائية يمكن أن تفعل ذلك في بعض الأحيان تحسين الخوارزميات لحل المشكلات الحتمية بطبيعتها - وهي نتيجة غير بديهية حيرت الباحثين لسنوات. عمل إمباجلياتزو مع منظر التعقيد آفي ويغدرسون وأظهر باحثون آخرون في التسعينيات أنه إذا كانت بعض المشكلات الحسابية صعبة في الأساس، فهذا يعني أنها ممكن دائما لتحويل الخوارزميات التي تستخدم العشوائية إلى خوارزميات حتمية. وعلى العكس من ذلك، إثبات أنه يمكن التخلص من العشوائية من أي خوارزمية سوف يثبت أيضا أن المشاكل الصعبة موجودة بالفعل.

كوانتا تحدث مع Impagliazzo عن الفرق بين المشكلات الصعبة والألغاز الصعبة، واستشارة الكهنة، والدروس الرياضية للكوميديا ​​الارتجالية. تم تكثيف المقابلة وتحريرها من أجل الوضوح.

متى بدأت الاهتمام بالرياضيات لأول مرة؟

لقد كنت مهتمًا بالرياضيات حتى قبل أن أعرف ما هي حقًا. في الصف الثالث، بدأت درجاتي في الرياضيات تتضاءل لأنه كان من المفترض أن نحفظ جدول الضرب، فرفضت. قالت والدتي: "لكن يا راسل، أنت تحب الرياضيات، لماذا لا تفعل هذا؟" فقلت: "هذه ليست رياضيات، إنها حفظ. الرياضيات الحقيقية لا تنطوي على الحفظ. كل ما تعلمته في تلك المرحلة كان الحساب، لذلك لست متأكدًا من أين حصلت على فكرة أن الرياضيات تدور حول مفاهيم مجردة.

ماذا عن علوم الكمبيوتر؟ أجزاء من هذا المجال مجردة للغاية، لكنها ليست ما يواجهه معظم الناس لأول مرة.

في المدرسة الثانوية، كنت قد حصلت على دورة برمجة في لغة BASIC، ولكن كان من الصعب حقًا إنجاز أي شيء. كان لا بد من نقل البرامج إلى أشرطة ورقية، والتي كان لا بد من تشغيلها من خلال هذا الكمبيوتر القديم جدًا الذي غالبًا ما يتعطل ويمزق ورقك إلى نصفين. لذلك اعتقدت أن علوم الكمبيوتر كانت مملة بشكل مخيف.

كنت أنوي دراسة المنطق. لكن الكثير من المفاهيم، عندما حاولت إضفاء طابع رسمي عليها، كانت تتضمن عمليات حسابية وخاصة حدود العمليات الحسابية. أسئلة مثل "كيف نعرف أن الأشياء في الرياضيات صحيحة؟" و"كيف نفهم صعوبة ممارسة الرياضيات؟" أدى إلى ظهور علوم الكمبيوتر النظرية، ونظرية التعقيد بشكل خاص.

تستكشف بعض أعمالك الأكثر شهرة الروابط بين التشفير ونظرية التعقيد الحسابي. لماذا يرتبط هذين المجالين؟

عندما تقوم بإعداد نظام تشفير، تحتاج إلى التمييز بين المستخدمين الشرعيين - الأشخاص الذين تريد منحهم حق الوصول - وأي شخص آخر. وتمنحنا المشكلات الصعبة حسابيًا طريقة لتمييز هذه المجموعات بناءً على ما يعرفونه. لكن إذا كنت تريد أن تكون معرفة إجابة مشكلة ما وسيلة للتمييز بين مجموعتين من الأشخاص، فلا يمكنك استخدام أي مسألة صعبة فحسب، بل تحتاج إلى لغز صعب.

ما الفرق بين المشكلة واللغز؟

بشكل عام، الشخص الذي يطرح المشكلة قد لا يعرف الإجابة. اللغز هو مشكلة مصممة مع وضع الإجابة في الاعتبار. فلماذا نحتاج اللغز؟ لأننا بحاجة إلى أن نكون قادرين على تحديد ما إذا كان الشخص الذي يفترض أنه حل المشكلة قد فعل ذلك بالفعل. في الحياة اليومية، نستخدم الألغاز للتسلية، ولكننا نستخدمها أيضًا في الفصول الدراسية لاختبار ما إذا كان الناس يفهمون المادة. هذا ما يحدث في التشفير: نحن نستخدم الألغاز لاختبار معرفة شخص ما.

الفرق بين العوالم الخمسة هو كيفية إجابتهم على الأسئلة "هل هناك مشاكل صعبة؟" و"هل هناك ألغاز صعبة؟"

كيف تظهر هذه الإجابات المختلفة؟

في العالم الأول، Algorithmica، لا توجد مشاكل صعبة. ليس عليك أن تعرف كيف صمم شخص ما مشكلتك: يمكنك دائمًا حلها. تقول هيوريستيكا: "حسنًا، ربما تكون بعض المشكلات صعبة." ثم نصل إلى بيسيلاند، حيث العديد من المشاكل صعبة، ولكن معظم الألغاز ليست كذلك. تقريبًا أي مشكلة أخترعها وأعرف حلها، ستكون قادرًا على حلها أيضًا. كل هذه العوالم سيئة بالنسبة للتشفير.

في Minicrypt، يمكنني إنشاء ألغاز أعرف كيفية حلها والتي لا تزال تمثل تحديًا حقيقيًا بالنسبة لك. وأخيرًا، Cryptomania هو عالم يمكن فيه لشخصين الوقوف في مكان عام حيث يمكن للمتنصت أن يسمع ويخلق معًا لغزًا لا يزال صعبًا على المتنصت.

ما الذي دفعك لكتابة ورقة العوالم الخمسة؟

في ذلك الوقت، كان من المعروف أن الإجابات المختلفة لسؤال P مقابل NP سيكون لها تأثير كبير على نوع المشكلات التي يمكننا حلها وأيضًا نوع الأمان الذي يمكن أن نأمل فيه، ولكن الفروق النوعية بين الأشكال المختلفة للسهولة والصعوبة لم تكن صلابة واضحة حقا.

كانت هناك ورقة بحثية ثاقبة للغاية قبل بضع سنوات فقط والتي حددت الفروق باستخدام العديد من الأسئلة المترابطة مع ما يقرب من 20 إجابة محتملة. أحد أسباب رغبتي في كتابة بحث العوالم الخمسة هو أننا حققنا قدرًا هائلاً من التقدم في تلك السنوات القليلة. سيكون من الصعب العثور على أسماء لعشرين عالمًا محتملاً.

فلماذا نؤطر الأمر بهذه الطريقة، كعوالم مختلفة بأسماء ملتوية؟

لقد وافقت على كتابة هذه الورقة للمؤتمر. كنت أسهر في وقت متأخر من الليل محاولًا معرفة ما سأقوله، وفي مكان ما حوالي الساعة الواحدة صباحًا، بدا أن تأطير العوالم المختلفة فكرة جيدة. ثم قرأتها في صباح اليوم التالي وما زالت تبدو وكأنها فكرة جيدة - لقد كانت طريقة لإظهار كيف ستؤثر هذه الأفكار فعليًا على العالم دون التورط في التفاصيل الكمية. ما يجعلني أسعد بشأن هذه الورقة هو أنني أسمع من الأشخاص الذين يقومون بأبحاث في مجال التعقيد أن هذه هي الورقة التي جعلتهم مهتمين بالمجال كطلاب جامعيين.

هل استبعد الباحثون أيًا من العوالم الخمسة المحتملة؟

نحن في الواقع نضيف المزيد، وقد بدأ الناس يتحدثون عنه غموض كعالم من أدوات التشفير الأقوى. إنه أمر محبط بعض الشيء أننا أحرزنا الكثير من التقدم في أواخر الثمانينيات ولم نتخلص من أي عوالم منذ ذلك الحين. لكن من ناحية أخرى، نحن نعرف الكثير عن الروابط بين العوالم ولدينا صورة أكثر وضوحا لما سيبدو عليه كل عالم.

وتلعب العوالم الافتراضية أيضًا دورًا آخر في نظرية التعقيد، في البراهين التي تفترض وجود “النبوءات”. لذا، أولاً وقبل كل شيء، ما هو أوراكل بالضبط؟

تخيل أن شخصًا ما يبني جهازًا مبتكرًا يمكنه حل بعض المشكلات دون أن نعرف خوارزمية لحل تلك المشكلة. هذا هو أوراكل. إذا كان لدينا مثل هذا الجهاز المعجزة ووضعناه داخل أجهزة الكمبيوتر لدينا، فإنه يمكن أن يتغير حيث الخط الفاصل بين ما هو قابل للحساب وما هو غير قابل للحساب.

هل يعتقد الباحثون أن هذه الصناديق السحرية يمكن أن تكون موجودة بالفعل؟

لا، ربما لا وجود لها. في وقت مبكر، كانت نتائج أوراكل مثيرة للجدل إلى حد ما لأنها افتراضية للغاية. ولكن إحدى الطرق التي يمكن أن تكون مفيدة للغاية هي عندما يتم استخدام أوراكل لنموذج الوضع المثالي. لنفترض أنك تحاول إظهار أن A لا يعني بالضرورة B. تبدأ بالإعداد الذي يكون لديك فيه أقصى A وتبين أن هذا لا يزال غير كافٍ لضمان B. إذا كان بإمكانك إظهار ذلك حتى لو كانت كل الاحتمالات لصالحك، لا تزال غير قادر على إثبات شيء ما، وهذا دليل قوي حقًا على أنه سيكون من الصعب إثباته.

لقد اكتشفت أيضًا روابط بين الصلابة الحسابية والعشوائية. كيف يعمل هذا الاتصال؟

إنها حقًا طريقة للقول إنه إذا كنت لا تفهم شيئًا ما، فقد يبدو الأمر عشوائيًا. لنفترض أنني قلت إنني أفكر في رقم يتراوح بين الواحد والألف. إذا اخترت الرقم عشوائيًا، فلديك فرصة واحدة في الألف لتخمينه. وإذا سألت - متبعًا مونتي بايثون - "بالميل في الساعة، ما هو متوسط ​​السرعة الجوية لطائر السنونو الأوروبي؟" لديك نفس الفرصة تقريبًا. ربما تسير بسرعة أكثر من ميل واحد في الساعة، ومن المحتمل ألا تتجاوز ألف ميل في الساعة.

هذا ليس في الواقع عشوائيًا - إنه سؤال يمكن الإجابة عليه بشكل حتمي. يمكننا فقط قياس جميع طيور السنونو التي تحلق حولنا، ولكن من الصعب تحديد ذلك في ظل الموارد المحدودة، مثل عدم وجود ميزانية لقياس سرعة طيور السنونو وعدم وجود عدد لا نهائي من طيور السنونو.

لذا فإن الفكرة هنا هي أن المسائل الصعبة التي لا نعرف حلولها يمكن أن توفر مصدراً لأرقام "عشوائية زائفة" تبدو عشوائية.

بالحديث عن مونتي بايثون، أعلم أنك تمارس الكوميديا ​​الارتجالية منذ فترة طويلة - كيف بدأت؟

بدأت العمل كأستاذ مساعد في سان دييغو عام 1991. وفي حوالي عام 94 أو نحو ذلك، فكرت: "ليس لدي الكثير من الحياة خارج القسم". لذلك حصلت على الجريدة الأسبوعية المجانية، ونظرت في قائمة الأندية والأنشطة. لقد استبعدت كل شيء باستثناء الكوميديا ​​المرتجلة - اعتقدت أنه من المعقول على الأقل أن أكون موافقًا عليها. التقيت بزوجتي في فصل المبتدئين.

ماذا تعتقد؟

تقول أنني كنت فظيعة حقا. عندما تكون منطقيًا، يتم تدريبك على التفكير دائمًا في الفروق الدقيقة في كل كلمة. أنت لا تريد أن تقول شيئا غير صحيح. الارتجال شيء عظيم لأنه يعكس ذلك: ليس الهدف أن تقول شيئًا مثاليًا، بل أن تختلق شيئًا بسرعة. لقد كان عكس بقية حياتي.

أخذت زوجتي الآن استراحة من الفصل، وعندما عادت بعد عام، تمكنت من إثارة إعجابها. كان ذلك قبل 30 عاما. ما زلت آخذ نفس الفصل مع نفس المدرب.

هل أدى التحسين إلى تغيير الطريقة التي تتعامل بها مع بحثك؟

إنها ممارسة جيدة ألا تكون مفرطًا في النقد بشأن كل فكرة لديك. وهذا مفيد بشكل خاص في عمليات التعاون. عندما كنت أعمل مع أشخاص آخرين، اعتدت أن أقول أشياء مثل: "لكن هذه الفكرة لن تنجح للسبب التالي. هذا ليس صحيحا حرفيا. في الارتجال، من المفترض دائمًا أن تقبل ما يقوله شريكك. وأعتقد أن هذا سلوك جيد، خاصة عندما تقوم بإجراء بحث مع الطلاب: لا ترفض شيئًا يقولونه لمجرد أنك تعلم أنه غير صحيح. هناك الكثير من الأفكار الجيدة التي ليست صحيحة بنسبة 100%.

مثل ماذا؟

عندما تحاول الحصول على حدس لمشكلة ما، فإن الشيء الوحيد الذي يساعدك هو البدء ببعض الافتراضات المبسطة. عادةً ما تكون هذه الافتراضات غير صحيحة، لكنها يمكن أن تساعدك في التوصل إلى خريطة طريق. قل: لو كان عندي فيل لتجاوزت الجبال. بالطبع، ليس لدي فيل. ولكن إذا فعلت ذلك، فإليك كيف سأفعل ذلك”. وبعد ذلك تدرك: "حسنًا، ربما لا أحتاج إلى فيل للقيام بهذه الخطوة. البغل سيكون جيدًا."

ماذا عن حبك لألعاب تمثيل الأدوار، هل أثر ذلك على عملك على الإطلاق؟

ربما لم يؤثر ذلك على كل أبحاثي، لكنه بالتأكيد أثر على بحثي عن العوالم الخمسة. لقد كان لدي دائمًا اهتمام عام بالفانتازيا والخيال العلمي والتوصل إلى عوالم مختلفة محتملة - كيف ستكون الأمور لو كان كل شيء مختلفًا؟

لماذا تعتبر ألعاب لعب الأدوار طريقة مقنعة لاستكشاف عوالم افتراضية؟

الأشخاص الذين يهتمون بالخيال التأملي اخترعوا دائمًا العوالم. يشتهر تولكين بذلك، وكان يتمتع بخيال هائل جعل عالمه يشعر بأنه يعيش فيه بالفعل. بالنسبة لأولئك منا الذين لا يتمتعون بقدر كبير من الخيال، فإن أفضل طريقة لتحقيق ذلك هي دعوة الأشخاص إلى محيطك ولعبة ما. هي طريقة للقيام بذلك. الآن ليس عالمي فقط. ربما بدأ الأمر كما تخيلته، ولكن تمامًا كما هو الحال في أي تعاون، نظرًا لمساهمات الجميع، فقد تطور الأمر إلى ما هو أبعد من ذلك.