هذه قيود صارمة للغاية ، لذلك لم يكن من الواضح أن الذاكرة الإضافية يمكن أن تكون مفيدة على الإطلاق. ولكن لدهشتهم ، أظهر Buhrman و Cleve أنه إذا قمت بتعديل البتات بالطريقة الصحيحة ، يمكنك حقًا الحصول على جاذبية حسابية إضافية من الذاكرة الكاملة.
وقال لوف ، الذي كان طالب دراسات عليا في مجموعة بوهرمان في ذلك الوقت ، “لقد كان هذا صدمة للجميع” ، وهو يعمل على سؤال الذاكرة مع زميله الطالب فلوريان سبيلمان. سرعان ما مدد الفريق النتيجة إلى فئة أكبر من المشكلات ، ونشر نتائجهم المشتركة في عام 2014.
قاموا بتسمية الحوسبة الحفزية الجديدة للإطار ، واستعارة مصطلح من الكيمياء. وقال راغوناث تيواري ، أحد منظري التعقيد في المعهد الهندي للتكنولوجيا ، كانبور: “بدون المحفز ، لم يكن رد الفعل قد استمر”. “لكن المحفز نفسه لا يزال دون تغيير.”
ليس بعيدًا عن الشجرة
واصلت مجموعة صغيرة من الباحثين تطوير الحوسبة الحفزية ، لكن لم يحاول أحد حتى تطبيقها على مشكلة تقييم الأشجار التي ألهمت في البداية مسعى Koucký. بالنسبة لهذه المشكلة ، كان السؤال المفتوح المتبقي هو ما إذا كان يمكن استخدام كمية صغيرة من الذاكرة للتخزين والحساب في وقت واحد. لكن تقنيات الحوسبة الحفزية اعتمدت على الذاكرة الإضافية الكاملة كبيرة جدًا. تقليص تلك الذاكرة والتقنيات لم تعد تعمل.
ومع ذلك ، لم يستطع أحد الباحثين الشباب المساعدة في التساؤل عما إذا كانت هناك طريقة لتكييف تلك التقنيات لإعادة استخدام الذاكرة في خوارزمية تقييم الأشجار. كان اسمه جيمس كوك ، وبالنسبة له ، كانت مشكلة تقييم الأشجار شخصية: ستيفن كوك ، منظري التعقيد الأسطوري الذي اخترعها ، هو والده. كان جيمس يعمل على ذلك في مدرسة الدراسات العليا ، على الرغم من أنه ركز في الغالب على مواضيع غير ذات صلة تمامًا. بحلول الوقت الذي واجه فيه ورقة الحوسبة الحفزية الأصلية في عام 2014 ، كان جيمس على وشك التخرج ومغادرة الأوساط الأكاديمية لهندسة البرمجيات. ولكن حتى عندما استقر في وظيفته الجديدة ، ظل يفكر في الحوسبة الحفزية.
قال: “كان علي أن أفهم ذلك وأرى ما يمكن القيام به”.
لسنوات ، تعرّض جيمس كوك مع نهج الحفاز لمشكلة تقييم الأشجار في أوقات فراغه. لقد تحدث عن تقدمه في ندوة 2019 تكريما لعمل والده الرائد في نظرية التعقيد. بعد الحديث ، اتصل به طالب دراسات عليا يدعى إيان ميرتز ، الذي وقع في حب الحوسبة الحفزية قبل خمس سنوات بعد أن علمت عنها كطالب شاب.
قال ميرتز: “لقد كان مثل سيناريو طبع الطائر”.
انضم كوك وميرتز إلى الجهود ، وسرعان ما دفعت جهودهم. في عام 2020 ، ابتكروا خوارزمية تحل مشكلة تقييم الأشجار بذاكرة أقل من الحد الأدنى اللازم للتخمين من قبل Elder Cook و McKenzie – على الرغم من أنه كان بالكاد أقل من تلك العتبة. ومع ذلك ، كان هذا يكفي لجمع الرهان 100 دولار ؛ مريح للطهاة ، بقي نصفها في الأسرة.
ولكن لا يزال هناك عمل للقيام به. بدأ الباحثون في دراسة تقييم الأشجار لأنه بدا كما لو أنه قد يقدم أخيرًا مثالًا على مشكلة في P ليست في L – بمعنى آخر ، مشكلة سهلة نسبيًا لا يمكن حلها باستخدام ذاكرة قليلة جدًا. استخدمت طريقة Cook و Mertz الجديدة ذاكرة أقل من أي خوارزمية لتقييم الأشجار الأخرى ، لكنها لا تزال تستخدم أكثر بكثير من أي خوارزمية لمشكلة في تقييم الأشجار L. ، ولكن ليس خارجها.
في عام 2023 ، خرج Cook و Mertz مع خوارزمية محسّنة استخدمت ذاكرة أقل بكثير – فهي أكثر من الحد الأقصى المسموح به للمشاكل في L. يشك العديد من الباحثين الآن في أن تقييم الأشجار في L بعد كل شيء ، وأن الدليل هو مجرد وقت. قد يحتاج منظري التعقيد إلى مقاربة مختلفة لمشكلة P مقابل L.
وفي الوقت نفسه ، فإن نتائج Cook و Mertz قد حفزت الاهتمام بالحوسبة الحفازة ، مع أعمال جديدة تستكشف الاتصالات إلى العشوائية وتأثيرات السماح ببعض الأخطاء في إعادة تعيين الذاكرة الكاملة إلى حالتها الأصلية.
وقال ماكنزي: “لم ننتهي من استكشاف ما يمكننا القيام به بهذه التقنيات الجديدة”. “يمكننا أن نتوقع المزيد من المفاجآت.”
القصة الأصلية أعيد طبعه بإذن من مجلة Quanta ، منشور مستقل تحريري ل مؤسسة سيمونز تتمثل مهمتها في تعزيز الفهم العام للعلوم من خلال تغطية التطورات البحثية والاتجاهات في الرياضيات والعلوم المادية والحياة.
