حل لغز عمره ٥٠ عامًا حول الزمان والمكان في الحوسبة

من المسائل المحورية في نظرية التعقيد الحسابي العلاقة بين P و PSPACE، وهما فئتان تضمان المسائل القابلة للحل في وقت ومساحة معقولتين، على التوالي. وبشكل حدسي، تُعد المساحة موردًا أكثر قوة من الزمن لأنها قابلة لإعادة الاستخدام. وعلى مدار ٥٠ عامًا، حاول الباحثون إثبات أن PSPACE أكبر من P، مما يعني أن بعض المسائل لا يمكن حلها بسرعة، ولكن يمكن حلها بمساحة محدودة. وقد حقق هوبكروفت وبول وفاليانت اكتشافًا في عام ١٩٧٥، أظهروا أن المساحة أقوى قليلاً من الزمن. ومع ذلك، فقد قُيِّد هذا التقدم بنهج "المحاكاة". وقد كسر ريان ويليامز الجمود أخيرًا من خلال نهج مبتكر، وحلّ المشكلة التي طال أمدها.