بالنسبة للخوارزميات ، تعد الذاكرة موردًا أقوى بكثير من الوقت

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

لمدة 50 عامًا ، افترض الباحثون أنه كان من المستحيل تحسين محاكاة Hopcroft و Paul و Valiant العالمية. فكرة وليامز – إذا نجحت – لن تتغلب على سجلهم – فهي ستهدمها.

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

في نهاية فبراير ، وضع ويليامز أخيرًا الورقة النهائية عبر الإنترنت. فوجئت كوك وميرتز مثل أي شخص آخر. قال ميرتز: “اضطررت للذهاب إلى المشي لفترة طويلة قبل القيام بأي شيء آخر”.

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

“لقد كنت معجبًا جدًا” ، قال Valiant. “إذا حصلت على أي نتيجة رياضية هي أفضل شيء منذ 50 عامًا ، فيجب أن تفعل شيئًا صحيحًا”.

PSPACE: الحدود النهائية

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

قال ويليامز: “لا يزال لدي صعوبة في تصديق ذلك”. “يبدو من الجيد جدًا أن يكون صحيحًا.”

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

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

وقال فاليانت: “قد يكون عنق الزجاجة النهائي ، أو قد يكون عنق الزجاجة لمدة 50 عامًا”. “أو قد يكون شيئًا ربما يمكن لشخص ما حله الأسبوع المقبل.”

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

وقال “لا يمكنني أبدًا إثبات الأشياء التي أريد إثباتها على وجه التحديد”. “لكن في كثير من الأحيان ، فإن الشيء الذي أثبتت أنه أفضل من ما أردت.”

ملاحظة المحرر: Scott Aaronson هو عضو في المجلس الاستشاري لمجلة Quanta.

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