P مقابل PSPACE: هل المساحة أكثر قوة حسابيًا من الزمن؟
2025-05-21
سؤال محوري في نظرية التعقيد هو العلاقة بين فئتي التعقيد P و PSPACE. تشمل P المشكلات القابلة للحل في وقت معقول، بينما يتعامل PSPACE مع تعقيد المساحة. الاعتقاد السائد هو أن PSPACE أكبر من P، نظرًا لإمكانية إعادة استخدام المساحة على عكس الزمن. لإثبات ذلك، يتطلب الأمر إظهار مشكلات في PSPACE غير قابلة للحل في وقت متعدد الحدود. تستعرض المقالة الاختراق الذي حدث عام 1975 على يد Hopcroft و Paul و Valiant، والذي أظهر تفوق المساحة بشكل طفيف على الزمن، لكن التقدم توقف. وقد كسر عمل Ryan Williams الجمود أخيرًا، مما أتاح رؤى جديدة لحل مشكلة P مقابل PSPACE.
التطوير
P مقابل PSPACE