یکی از دانشمندان علوم کامپیوتر، اثباتی "خیره کننده" ارائه داده که در پنجاه سال گذشته، نخستین پیشرفت در خصوص یکی از مشهورترین پرسش‌ها در این رشته است.
بعد از ظهر یکی از روزهای جولای 2024، رایان ویلیامز تصمیم گرفت به خودش اثبات کند که اشتباه می‌کند. دو ماه از کشف شگفت انگیزش درباره رابطه میان زمان و حافظه در رایانه‌ها گذشته بود. یک پیش‌نویس از اثبات ریاضی وجود داشت که نشان می‌داد حافظه، قدرتمند تر از آن چیزی بود که دانشمندان کامپیوتر باور داشتند: حتی مقدار کمی حافظه می‌تواند به اندازه‌ زمانی بسیار زیاد، موثر و مفید باشد.
این ایده چنان غیرممکن بود که او فرض می‌کرد حتما یک اشتباهی رخ داده و فورا اثبات را کنار گذاشت تا به ایده‌های "کمتر دیوانه وار" بپردازد. اکنون زمانی برای بررسی دقیق آن یافت.

بعد از چند ساعت بررسی دقیق، ویلیامز نتوانست حتی یک خطا در استدلالش بیابد.
-" فکر می‌کردم عقلم را از دست داده‌ام"؛ ویلیامز، نظریه‌پرداز علوم کامپیوتر در مؤسسه فناوری ماساچوست، برای اولین‌بار پذیرفت که شاید، فقط شاید، حافظه واقعا به قدر آنچه اثباتش نشان می‌دهد، قدرتمند باشد.
ماه‌ها بعد، جزئیات اثباتش را کامل کرد، هر مرحله را بررسی کرد و از جمعی از پژوهشگران بازخورد گرفت.
در ماه فوریه، او نهایتا اثباتش را به صورت آنلاین منتشر کرد و بازخورد گسترده‌ای دریافت نمود.
اوی ویگدرسون، نظریه‌ پرداز علوم کامپیوتر در موسسه مطالعات پیشرفته پرینستون، گفت:" این شگفت انگیز است، زیباست." او پس از شنیدن خبر، فوری به ویلیامز ایمیل تبریک فرستاد، " مغزم را منفجر کردی."

زمان و حافظه (که گاهی آن را فضا یا space  می‌نامند) دو منبع بنیادی در محاسبات‌اند :

هر الگوریتمی برای اجرا شدن به جز زمان، به حافظه نیز نیاز دارد تا داده‌ها را در آن ذخیره کند. تا پیش از این، همه الگوریتم‌های شناخته شده برای انجام برخی وظایف نیازمند فضایی تقریبا متناسب با زمانشان بودند و پژوهشگران همواره فرض می‌کردند که راهی بهتر از این وجود ندارد. اما اثبات ویلیامز نشان داد که می‌توان هر الگوریتم را – صرف نظر از کاری که انجام می‌دهد – به شکلی بازسازی کرد که از حافظه بسیار کمتری استفاده کند.

رایان ویلیامز همکارانش را با اثباتی برجسته در مورد رابطه بین زمان و مکان در محاسبات شگفت‌زده کرد.

علاوه بر این، نتیجه اول – یعنی اینکه چه کاری می‌توان با مقدار مشخصی حافظه انجام داد – خود به یک نتیجه ثانویه می‌ انجامد: یعنی اینکه چه کاری را نمی‌توان در زمان مشخص انجام داد.
این نتیجه دوم در واقع تعجب‌آور نیست: پژوهشگران انتظارش را داشتند اما نمی‌دانستند چگونه اثباتش کنند. راه‌ حل ویلیامز، که بر پایه‌ی نتیجه گسترده اولیه‌اش بنا شده، تقریبا به طرز اغراق‌آمیز و غیر واقعی‌ای افراطی بنظر می‌رسید – انگار برای اثبات گناه یک مظنون قاتل، برای تک تک آدم‌های دیگر روی کره زمین یک عذر غیبت محکم و بدون نقص جور کنیم. با این حال، این دستاورد می‌تواند راهی نو برای حمله به یکی از کهن‌ترین مسائل حل نشده در علوم کامپیوتر فراهم کند.

پل بیم، دانشمند علوم کامپیوتر از دانشگاه واشنگتن گفت:" این واقعا نتیجه‌ای شگفت انگیز و یک پیشرفت بزرگ است و البته خیلی جای تعجب ندارد که کسی مثل رایان ویلیامز چنین کاری کرده باشد."

فضایی برای جولان

ویلیامز، 46 ساله، چهره‌ای گویا و پر از احساس دارد و رگه‌ای از موهای خاکستری در میان موهایش دیده می‌شود. دفتر کار او که مشرف به مناره‌های رنگارنگ مرکز استاتا در دانشگاه MIT است، نمونه‌ای دیگر از استفاده خلاقانه از فضاست. دو مت یوگا، طاقچه پنجره را به گوشه‌ای دنج برای مطالعه تبدیل کرده و میز کار در گوشه‌ای با شکلی غیرمعمول جا داده شده است تا جا برای یک کاناپه فراهم شود؛ کاناپه‌ای که رو‌به‌روی یک تخته سفید قرار دارد؛ تخته‌ای پر از یادداشت‌ها و فرمول‌های ریاضی.

دانشگاه MIT فاصله زیادی با خانه دوران کودکی ویلیامز، منطقه‌ای روستایی در آلاباما داشت. جایی که کمبودی از نظر فضا وجود نداشت. او در یک مزرعه 50 جریبی بزرگ شد و در سن 7 سالگی، زمانی که مادرش او را برای شرکت در یک کلاس تقویتی ویژه‌ی تحصیلی، به آن سر شهرشان برد، برای نخستین بار یک کامپیوتر دید. او به یاد می‌آورد که مجذوب یک برنامه ساده شده بود، برنامه‌ای که آتش بازی دیجیتال را نمایش می‌داد. ویلیامز می‌گوید: "برنامه، یک رنگ را به صورت تصادفی انتخاب می‌کرد و آن را از مرکز صفحه نمایش، به جهتی تصادفی می‌فرستاد، نمی‌توانستی حدس بزنی در نهایت چه تصویری به وجود خواهد آمد."

دنیای رایانه‌ها، شبیه یک زمین بازی شگفت‌انگیز و دیوانه‌وار بنظر می‌رسید؛ پر از احتمالات بی نهایت.

ویلیامزِ نوجوان، کاملا شیفته آن دنیا شده بود. او می‌گوید": برای خودم، روی کاغذ برنامه‌هایی می‌نوشتم تا در آینده آن‌ها را روی یک کامپیوتر اجرا کنم، والدینم واقعا نمی‌دانستند باید با من چه‌کار بکنند."

با گذشت زمان و بزرگ‌تر شدن ویلیامز‌، او از کامپیوترهای خیالی به سراغ کامپیوترهای واقعی رفت. برای دو سال پایانی دبیرستان، به مدرسه‌ی ریاضی و علوم آلاباما انتقال یافت، یک مدرسه شبانه روزی دولتی و معتبر، جایی که برای نخستین بار با جنبه علوم نظری علوم کامپیوتر آشنا شد. او می‌گوید": متوجه شدم که دنیایی بسیار وسیع‌تر، آن بیرون وجود دارد، و می‌شود در مورد کامپیوتر از جنبه ریاضی نیز فکر کرد. او گفت: "و این همان کاری بود که دلم می‌خواست انجام بدم."

ویلیامز به طور ویژه جذب شاخه‌ای از علوم کامپیوتری نظری به نام نظریه پیچیدگی محاسباتی شده بود. این شاخه به منابعی مانند زمان و فضا (حافظه) می‌پردازد که برای حل مسائل محاسباتی، مانند مرتب سازی فهرست‌ها یا تجزیه عددها به عوامل اول، لازم است. بیشتر مسائل را می‌توان با الگوریتم های مختلفی حل کرد، که هر کدام نیازهای خاص خود را از نظر زمان و فضا دارند. نظریه پردازان پیچیدگی مسائل را در دسته بندی هایی قرار می‌دهند که به آن کلاس‌های پیچیدگی گفته می‌شود، و این دسته بندی‌ها بر اساس میزان منابعی است که بهترین الگوریتم‌ها برای حل مسائل نیاز دارند – یعنی الگوریتم‌هایی که کارآمد ترین زمان اجرا را دارند یا کمترین حافظه را مصرف می‌کنند–.

اما چگونه می‌توان مطالعه منابع محاسباتی را به صورت ریاضی و دقیق انجام داد؟ اگر سعی کنید زمان و فضا را با مقایسه‌ی دقیقه‌ با مگابایت تحلیل کنید، به جایی نخواهید رسید. برای هرگونه پیشرفت، باید با تعاریف درست و اصولی شروع کرد. 

خلاقیت در مدیریت منابع

"این کار به شکلی اغراق‌آمیز و کارتونی، افراطی بنظر می‌رسد – مثل این می‌ماند که برای اثبات گناه یک مظنون قاتل، برای همه مردم دیگر روی کره زمین یک عذر غیبت محکم فراهم کنی."

این تعاریف، (از زمان و فضا در نظریه پیچیدگی) از کارهای یوریس هارتمانیس، یکی از پیشگامان علوم کامپیوتر، سرچشمه گرفت؛ کسی که تجربه زیادی در کنار آمدن با منابع محدود داشت.

او در سال 1928 در خانواده‌ای سرشناس در کشور لتونی به دنیا آمد، اما دوران کودکی‌اش با آغاز جنگ جهانی دوم بهم ریخت. نیروهای اشغالگر شوروی، پدرش را بازداشت و اعدام کردند، و پس از پایان جنگ، هارتمانیس دبیرستان را در یک اردوگاه پناهندگان به پایان رساند. در نهایت او وارد دانشگاه شد و با وجود آن‌ که توان خرید کتاب درسی نداشت، در تحصیل بسیار موفق بود. او در مصاحبه ای در سال 2009 به یاد آورد: " این کمبود را با یادداشت برداری ‌بسیار دقیق در کلاس ها جبران می‌کردم، این که مجبور باشی بداهه عمل کنی و بر سختی‌ها غلبه کنی، خودش نوعی مزیت است."

هارتمانیس در سال 1949 به ایالات متحده مهاجرت کرد و برای گذران زندگی، مشاغل متفاوتی برگزید – از ساخت ماشین‌آلات کشاورزی گرفته تا تولید فولاد، حتی به عنوان پیشخدمت شخصی (باتلر) مشغول به کار شد و همزمان در دانشگاه کانزاس سیتی، ریاضیات می‌خواند. در نهایت او وارد حوزه نوپای علوم نظری کامپیوتر شد و مسیر حرفه‌ای فوق‌العاده ای را طی کرد.

در سال 1960، زمانی که هارتمانیس در آزمایشگاه تحقیقاتی شرکت جنرال الکتریک در شهر اسکنکتدی ایالت نیویورک کار می‌کرد، با ریچارد استیرنز آشنا شد؛ دانشجوی تحصیلات تکمیلی‌ای که در آن تابستان، دوره کارآموزی خود را می‌گذراند. این دو نفر، در مجموعه‌ای از دو مقاله تحول‌آفرین، تعریف‌های دقیق ریاضی برای "زمان" و "فضا" ارائه کردند. این تعاریف زبان مشترکی را در اختیار پژوهشگران قرار داد تا بتوانند زمان و حافظه را با یکدیگر مقایسه کرده و مسائل را درکلاس‌های پیچیدگی مختلف طبقه بندی کنند.

در دهه 1960، یوریس هارتمانیس تعریف هایی را پایه گذاری کرد که دانشمندان علوم کامپیوتر برای تحلیل زمان و حافظه از آن‌ها استفاده می‌کنند.

یکی از مهم‌ترین کلاس‌ها، با نام ساده P  شناخته می‌شود. به طور تقریبی، این کلاس‌ها شامل تمام مسائلی است که می‌توان آن‌ها را در مدت زمان معقولی حل کرد. کلاس مشابهی برای حافظه وجود دارد که “ PSPACE” نامیده می‌شود. هر مسئله‌ای که در کلاس P قرار دارد، به صورت خودکار در کلاس PSPACE نیز قرار می‌گیرد، زیرا الگوریتم‌هایی که سریع اجرا می‌شوند، برای پر کردن حافظه کامپیوتر، زمان زیادی ندارند. اگر عکس این جمله هم درست بود، آن‌گاه این دو کلاس برابر محسوب می‌شدند: یعنی فضا و زمان از نظر قدرت محاسباتی برابر تلقی می‌شدند.

اما نظریه پردازان معتقدند که PSPACE کلاسی به مراتب بزرگ‌تر است و در برگیرنده مسائلی‌ست که در P جای نمی‌گیرد.  به عبارت دیگر، باور دارند که حافظه (فضا) یک منبع محاسباتی است که به مراتب نیرومند‌تر از زمان است. این واقعیت از این باور ناشی می‌شود که الگوریتم ها می‌توانند از یک بخش کوچک حافظه، بارها و بارها استفاده کنند، در حالی که زمان این بخشندگی را ندارد – وقتی که گذشت؛ دیگر قابل بازگرداندن نیست. ویلیامز گفت:" این شهود واقعا ساده‌ست، می‌‌توانی از حافظه دوباره استفاده کنی، از زمان نه."

اما شهود برای نظریه پردازان پیچیدگی کافی نیست؛ آن‌ها به دنبال اثبات دقیق هستند. برای اینکه اثبات کنند PSPACE ازp بزرگ‌تر است، پژوهشگران باید نشان دهند که برای بعضی مسائل در PSPACE، الگوریتم‌های سریع به طور اصولی غیرممکن‌اند. اما از کجا باید شروع کرد؟

اودیسه‌ای در فضا

همه چیز از دانشگاه کرنل شروع شد، جایی که هارتمانیس در سال 1965 به آنجا رفت تا ریاست گروه تازه تاسیس علوم کامپیوتر را بر عهده بگیرد. با مدیریت او، این گروه به سرعت به یکی از قطب‌های پژوهش در نظریه پیچیدگی محاسباتی تبدیل شد، و اوایل دهه 1970، دو پژوهشگر حاضر در آن گروه به نام جان هاپکرفت و ولفگانگ پاول، تصمیم گرفتند ارتباط دقیقی میان زمان و حافظه برقرار کنند.

هاپکرفت و پاول می‌دانستند برای حل مسئله‌ی P در برابر PSPACE باید اثبات کنند که انجام برخی محاسبات در زمان محدود ممکن نیست. اما اثبات این مسئله دشوار است. در عوض تصمیم گرفتند تا این مسئله را برعکس کرده و بررسی کنند که با حافظه محدود انجام چه کارهایی ممکن است. هدفشان این بود که نشان دهند الگوریتم‌هایی که حافظه محدودی دارند، قابلیت حل کردن مسائلی را دارند که الگورتیم‌های دیگر با "مقدار اندکی زمان" بیشتر حل می‌کنند. این موضوع نشان می‌داد که حافظه (فضا)، دست کم، کمی قوی تر از زمان است – گامی کوچک اما ضروری برای اثبات اینکه PSPACE از P بزرگ‌تر است. با داشتن این هدف در ذهنشان، آن‌ها به سراغ روشی رفتند که نظریه‌پردازان پیچیدگی، آن را "شبیه‌سازی" یا "SIMULATION" می‌نامند. روشی که الگوریتم‌های موجود را به الگوریتم‌های جدیدی تبدیل می‌کند که همان مسئله را حل می‌کنند اما با ترکیب متفاوتی از حافظه و زمان.

برای درک این ایده، تصور کنید یک الگوریتم سریع در اختیار دارید که کتاب‌هایتان را به ترتیب حروف الفبا مرتب می‌کند، اما برای انجام این کار باید کتاب‌هایتان را در چندین کپه کوچک، روی زمین پخش کنید. ممکن است روشی را انتخاب کنید که جای کمتری را در آپارتمان تان اشغال کند، حتی اگر زمان بیشتری ببرد. شبیه‌سازی، فرایند ریاضیاتی‌ای است که می‌توان از آن برای بدست آوردن یک الگوریتم مناسب‌تر استفاده کرد: الگوریتم اصلی را به او تحویل دهید و درعوض یک الگوریتم جدیدی به شما تحویل می‌دهد که حافظه کمتری مصرف می‌کند، تنها با صرف زمان بیشتر. طراحان الگوریتم مدت زمان زیادی‌ست که این مبادله زمان – حافظه را برای کارهای خاصی مانند مرتب‌سازی، مورد بررسی قرار داده‌اند. اما برای برقراری یک رابطه کلی میان زمان و فضا، هاپکرفت و پاول به چیزی فراگیر‌تر نیاز داشتند: یک روش شبیه سازی که در مصرف حافظه صرفه‌جویی کند و برای هر الگوریتمی – فارغ از اینکه آن الگوریتم چه مسئله‌ای را حل می‌کند – کار کند. طبیعتا انتظار داشتند که این کلیت و جامعیت، بهایی هم داشته باشد. چنین شبیه‌سازی همگانی‌ای نمی‌تواند از جزئیات خاص هر مسئله‌ای استفاده کند، بنابراین به احتمال زیاد، به اندازه شبیه‌سازی‌های تخصصی، صرفه‌جویی نخواهد کرد. اما زمانی که هاپکرافت و پاول کارشان را شروع کردند، هیچ روش بین‌المللی شناخته شده‌ای برای صرفه‌جویی در حافظه وجود نداشت. حتی صرفه‌جویی به مقدار اندک نیز پیشرفت بزرگی محسوب می‌شد. پیشرفت بزرگ در سال 1975 اتفاق افتاد، زمانی که هاپکرفت و پاول با پژوهشگری جوان به نام لزلی ولینت همکاری کردند. این سه نفر روشی جامع برای شبیه‌سازی ابداع کردند که به طور کلی مقدار اندکی از حافظه را صرفه‌جویی می‌کرد. فرقی نمی‌کرد چه الگوریتمی را وارد سیستم کنید، نتیجه، یک الگوریتمی بود که بودجه حافظه اش کمی کمتر از بودجه زمانی الگوریتم اصلی بود.

" هر کاری که بتوانی در مقدار مشخصی از زمان انجام دهی، با حافظه کمتر هم می‌توانی انجام دهی." - لزلی ولینت
این نخستین گام بزرگ در تلاش برای پیوند دادن حافظه و زمان در نظریه پیچیدگی بود.

در سال 1975، لزلی ولینت کمک کرد تا اثبات شود که حافظه (فضا) به نسبت زمان، منبع محاسباتی نیرومند‌تری است.

اما سپس، روند پیشرفت متوقف شد، نظریه‌پردازان پیچیدگی دچار تردید شدند که شاید به یک مانع بنیادی برخورد کرده‌اند. مشکل، دقیقا به ماهیت همگانی و جامع شبیه‌سازی ارائه شده توسط هاپکرافت و پاول باز می‌گشت. با اینکه بسیاری از مسائل را می‌توان با فضای حافظه‌ای بسیار کمتری نسبت به زمان لازم حل کرد، اما به‌نظر می‌رسید که برخی مسائل، تقریبا به همان اندازه‌ای که به زمان نیاز دارند، نیازمند حافظه (فضا) نیزهستند. اگر اینطور باشد، شبیه‌سازی همگانی‌ای که حافظه را بهتر مدیریت می‌کند، غیرممکن خواهد بود. زمانی نگذشت که پاول و دو پژوهشگر دیگر، ثابت کردند که چنین شبیه‌سازی‌هایی حقیقتا غیرممکن هستند. البته به شرطی که یک فرض به ظاهر بدیهی را بپذیریم: اینکه بخش‌های متفاوتی از داده، نمی‌توانند به صورت هم‌زمان در یک فضای مشترک از حافظه قرار بگیرند.

ویگدرسون گفت:" همه فرض می‌کردند که نمی‌شود کار از این بهتر انجام داد."

نتایج پاول نشان می‌داد که برای حل مسئله P در برابر PSPACE باید به طور کلی، ایده شبیه‌سازی را کنار گذاشت و به سراغ رویکردی متفاوت رفت، اما هیچ‌کس ایده خوبی نداشت. و این‌گونه بود که در این مسئله برای 50 سال بسته باقی ماند – تا اینکه در نهایت ویلیامز این در را باز کرد. البته اول باید دوران دانشگاه را پشت‌سر می‌گذاشت.

کلاس های پیچیدگی

در سال 1996، نوبت به ویلیام رسید که برای ورود به دانشگاه اقدام کند. او می‌دانست که دنبال کردن نظریه پیچیدگی، او را به مکان‌های دوری خواهد برد، اما پدر و مادرش مشخص کرده بودند که ساحل غربی آمریکا و کشور کانادا به طور کل منتفی است. در میان گزینه‌های باقی مانده، دانشگاه کرنل برایش برجسته‌تر از دیگر گزینه‌ها بود، زیرا در تاریخچه رشته مورد علاقه‌اش (نظریه پیچیدگی) جایگاه مهمی داشت.

او به یاد می‌آورد که با خود فکر می‌کرد:" این مرد، هارتمانیس، کلاس‌های پیچیدگی زمان و فضا را تعریف کرده، این موضوع برای من خیلی مهم بود."

ویلیامز با بورسیه مالی قابل توجهی در دانشگاه کرنل پذیرفته شد و در پاییز سال 1997، با این هدف که نظریه‌پرداز پیچیدگی شود؛ به آنجا رفت. این تمرکز و هدف‌مندی باعث شد در نظر همکلاسی‌هایش کاملا متمایز و برجسته به‌نظر برسد.

اسکات ارونسون دانشمند علوم کامپیوتر در دانشگاه تگزاس آستین، که دوران حضورش در کرنل با ویلیامز یکی بوده، گفت:" او واقعا شیفته نظریه پیچیدگی بود."

تا سال دوم دانشگاه، ویلیامز در تلاش برای هم‌پا شدن با درس‌هایی بود که بر دقت ریاضی تکیه داشتند نه شهود. پس از آن‌که در یک درس مربوط به نظریه محاسبات نمره متوسط گرفت، استاد آن درس به او پیشنهاد داد تا به دنبال مسیر شغلی دیگری برود. اما ویلیامز حاضر نبود رویای خود را کنار بگذارد. او مصمم‌تر شد و در یک درس نظری سطح کارشناسی ارشد ثبت‌نام کرد، به این امید که نمره‌ای درخشان در یک درس سخت، در پرونده درخواست تحصیلات تکمیلی‌اش تاثیرگذار باشد. استاد آن درس کارشناسی ارشد، هارتمانیس بود، که در آن زمان یکی از پیشکسوتان و چهره‌های بزرگ در این حوزه به ‌شمار می‌رفت. ویلیامز به صورت هفتگی در ساعات اداری هارتمانیس، او را ملاقات می‌کرد، به طور تقریبی او تنها دانشجویی بود که در آنجا حضور پیدا می‌کرد. پشتکارش نتیجه داد: در آن درس نمره (A) عالی گرفت. هارتمانیس پذیرفت که در ترم بعد، استاد راهنمای او در یک پروژه تحقیقاتی مستقل باشد. هارتمانیس او را تشویق کرد که رویکردی شخصی و منحصر‌به فرد در پژوهش‌های نظریه پیچیدگی پرورش دهد، و با ملایمت او را از مسیرهای بن‌بست و بی نتیجه دور نگه داشت. ویلیامز گفت:" در آن زمان به شدت تحت تاثیرش قرار گرفتم، فکر می‌کنم هنوز هم هستم."

با وجود آن‌که ویلیامز موفق به دریافت تحقیقاتی ارزشمند بنیاد ملی علوم آمریکا (NSF) شده بود، تمامی برنامه‌های دکترایی که برایشان درخواست داده بود، او را رد کردند. وقتی هارتمانیس این خبر را شنید، با یکی از همکارانش تماس گرفت، سپس به ویلیامز تبریک گفت که در یک برنامه کارشناسی ارشد یک ساله در دانشگاه کرنل پذیرفته شده. یک سال بعد ویلیامز دوباره به برنامه‌های دکترا درخواست داد و این بار با توجه به تجربه تحقیقاتی‌ای که کسب کرده بود، موفق شد. ویلیامز در دوران تحصیلات تکمیلی و سال‌های بعد از آن به کار در زمینه نظریه پیچیدگی ادامه داد. در سال 2010، چهار سال پس از دریافت مدرک دکتری، به نتیجه مهمی دست یافت – گامی کوچک، اما بزرگترین گامی که در چند دهه اخیر، برای حل مشهورترین پرسش در علوم کامپیوتر نظری برداشته شده بود. این دستاورد، جایگاه ویلیامز را تثبیت کرد و او در ادامه، ده‌ها مقاله درموضوعات مختلفی از نظریه پیچیدگی نوشت.

مساله  P در برابر PSPACE در میان مقالات نوشته شده نبود. ویلیامز از زمان اولین برخوردش با این مساله در دوران دانشگاه، مجذوب آن شده بود.
او حتی برنامه درسی علوم کامپیوترش را، به امید یافتن الهام از دیدگاه‌های دیگر درباره زمان و فضا، با درس‌هایی نظیر منطق و فلسفه تکمیل کرده بود. اما نتیجه‌ای حاصل نشد.

ویلیامز گفت:" این مسئله همیشه در گوشه ذهنم بوده، تنها نمی‌توانستم حرفی جالب درباره‌اش پیدا کنم که ارزش گفتن داشته باشد." او سرانجام، در سال گذشته فرصتی که در انتظارش بود را پیدا کرد.

سنگ‌ریزه‌های نرم و فشردنی

داستان نتیجه ویلیامز، یک سوال متفاوت درباره حافظه در محاسبات را به‌وجود آورد:
چه مسائلی را می‌توان با حافظه بسیار محدود حل کرد؟

در سال 2010، نظریه‌پرداز پیشگام پیچیدگی، استیفن کوک و همکارانش مسئله‌ای به نام "مسئله ارزیابی درخت" را مطرح کردند، آن‌ها اثبات کردند که هیچ الگوریتمی با بودجه فضایی کمتر از یک حد مشخص نمی‌تواند آن را حل کند. اما یک شکافی وجود داشت، این اثبات بر همان فرضیه متعارف و عقلانی که پل و همکارانش چند دهه پیش مطرح کرده بودند، تکیه داشت: الگوریتم‌ها نمی‌توانند داده‌های جدید را در فضایی که از قبل پر شده است، ذخیره کنند.

بیش از یک دهه، نظریه‌پردازان پیچیدگی تلاش کردند این شکاف را ببندند. سپس در سال 2023، جیمز کوک (فرزند استیفن کوک) و پژوهشگری به نام ایان مرتز آن شکاف را کاملا باز کردند، آن‌ها الگوریتمی طراحی کردند که مسئله ارزیابی درخت را با استفاده از فضای حافظه کمتری نسبت به آنچه تصور می‌شد حل کرد. اثبات استیفن کوک (پدر) این فرض را داشت که "بیت‌های داده" سنگریزه‌هایی هستند که باید جایگاه‌های جداگانه‌ای در حافظه الگوریتم اشغال کنند، اما مشخص شد که این تنها روش ذخیره‌سازی داده نیست.

بیم گفت:" در واقع می‌توانیم این سنگریزه‌ها را به گونه‌ای تصور کنیم که بشود آن‌ها را بهم فشرد."

جیمز کوک (چپ) و رایان مرتز به تازگی الگوریتمی را طراحی کردند که یک مسئله خاص را با استفاده بسیار کمتری از آنچه انتظار می‌‎رفت، حل می‎‌‌‌‌‌کند.

کوک و مرتز الگوریتمی طراحی کردند که کنجکاوی بسیاری از پژوهشگران را برانگیخت، اما مشخص نبود که این الگوریتم، کاربردی فراتر از مسئله ارزیابی درخت دارد یا نه. ویگدرسون گفت:" هیچ‌کس نمی‌دید که این موضوع چقدر برای مسئله زمان در برابر فضا مهم است." رایان ویلیامز استثنا بود. در بهار 2024، گروهی از دانشجویان، به عنوان پروژه نهایی یک درس که او تدریس می‌کرد، در باره مقاله کوک و مرتز ارائه‌ای داشتند. شور و اشتیاق آن‌ها باعث شد او با دقت بیشتری به این موضوع بپردازد. به محض اینکه او این کار را کرد، ایده‌ای به ذهنش رسید، او متوجه شد که روش کوک و مرتز در واقع ابزاری همگانی برای کاهش مصرف فضا است.

چرا از آن فضا استفاده نکنیم که شبیه‌سازی همگانی‌ جدیدی که زمان و فضا را به هم مرتبط می‌کند – مانند شبیه‌سازی‌ای که هاپکرافت، پل و الیانت طراحی کرده بودند، اما بهتر؟
این نتیجه کلاسیک روشی بود برای تبدیل کردن هر الگوریتمی با بودجه زمانی مشخص به الگوریتمی جدید با بودجه فضایی کمی کمتر.

ویلیامز دید که شبیه‌سازی مبتنی بر" سنگریزه‌های نرم" مصرف فضای الگوریتم جدید را به شکل قابل توجهی کاهش می‌دهد – این کاهش تقریبا برابر با جذر بودجه زمانی الگوریتم اصلی است.
این الگوریتم جدید که فضای کمی اشغال می‌کرد، بسیار کندتر هم بود، بر این اساس این شبیه‌سازی به احتمال زیاد کاربرد علمی نداشت. اما از دیدگاه نظری، این پیشرفت، دست کمی از یک انقلاب نبود.

به مدت 50 سال پژوهشگران بر این باور بودند که بهبود شبیه‌سازی همگانی هاپکرافت، پل و والینت غیرممکن است. ایده ویلیامز اگر جواب می‌داد – نه تنها رکورد آن‌ها را می‌شکست، بلکه آن را در هم می‌کوبید. ویلیامز گفت:" به این قضیه فکر کردم و گفتم، خب این نمی‌تواند درست باشد." او این مسئله را کنار گذاشت و تا آن روز ژوئیه به سراغش برنگشت – زمانی که سعی کرد اشکالی در استدلالش پیدا کند اما موفق نشد. پس از آن‌که فهمید هیچ ایرادی وجود ندارد، ماه‌ها وقت صرف کرد تا اثباتش را بنویسد و بازنویسی کند، تا آن را تا جایی که ممکن بود، شفاف و قابل فهم کند.

در پایان ماه فوریه، ویلیامز سر‌انجام مقاله نهایی شده را به صورت آنلاین منتشر کرد. کوک و مرتز به اندازه دیگران شگفت‌زده شدند. مرتز گفت:" قبل از اینکه بتوانم کاری انجام دهم، مجبور شدم به یک پیاده روی طولانی بروم." والیانت در مسیر رفت و آمد صبحگاهی‌اش، پیش نمایشی از بهبود ویلیامز، روی نتیجه‌ای که خودش سال‌ها پیش بدست آورده بود؛ دریافت کرد. او سال‌ها در دانشگاه هاروارد تدریس کرده – درست پایین‌تر از خیابانی که دفتر ویلیامز در  MIT قرار داشت. ‌آن‌ها سال‌ها پیش یکدیگر را دیده بودند، اما تا یک روز برفی در ماه فوریه، چند هفته پیش از علنی شدن نتیجه، که تصادفا در اتوبوس به هم برخوردند، نمی‌دانستند که در یک محله زندگی می‌کنند. ویلیامز اثباتش را برای والیانت  توضیح داد و به او قول داد تا مقاله‌اش را برایش بفرستد، والیانت گفت:" من واقعا تحت تاثیر قرار گرفتم. اگر به نتیجه‌ای ریاضیاتی دست‌یابی که بهترین دستاورد در 50 سال اخیر است، حتما یک جای کار، مسیر درستی را رفته‌ای."

PSPACE : مرز نهایی

ویلیامز با شبیه‌سازی به دست آمده جدیدش، نتیجه مثبت درباره توان محاسباتی"فضا" بدست آورد. الگوریتم‌هایی که از فضای نسبتا کمی استفاده می‌کنند، می‌توانند تمام مسائلی که به مقدار زمان بیشتری نیاز دارند را حل کنند. سپس تنها با چند خط محاسبه ریاضی، نتیجه بدست آمده را وارونه کرده و به نتیجه بدست آمده منفی درباره توان محاسباتی "زمان" رسید: برخی مسائل را نمی‌توان حل کرد، مگر اینکه زمان بیشتری نسبت به فضا صرف شود.
این نتیجه دوم و محدودتر، به انتظارات پژوهشگران نزدیک‌تر بود.

نکته عجیب ماجرا اینجاست که ویلیامز چطور به این نتیجه رسید – صرف نظر از اینکه الگوریتم‌ها چه مسائلی را حل می‌کنند، او ابتدا نتیجه‌ را اثبات کرد که درباره تمامی الگوریتم‌ها صدق می‌کند. ویلیامز گفت :" هنوز هم باورش برایم سخت است، برای واقعی بودن زیادی خوب است."

اگر بخواهیم به صورت کیفی بیان کنیم، نتیجه دوم ویلیامز، ممکن است پاسخی باشد برای مسئله  P دربرابر PSPACE.
تفاوت، در مقیاس نهفته است. P  و PSPACE کلاس‌های پیچیدگی بسیار گسترده‌ای هستند، در حالی که نتایج ویلیامز در سطحی دقیق‌تر و جزئی تر عمل می‌کنند. او شکاف کمّی‌ای میان توان محاسباتی فضا و زمان ایجاد کرد. و برای اینکه اثبات شود PSPACE از P بزرگ‌تر است، پژوهشگران باید این شکاف را بسیار، بسیار گسترده‌تر کنند.

این یک چالش دلهره‌آور است، تجربه‌ای شبیه به اینکه بخواهید شکافی در پیاده رو را با یک اهرم فلزی آنقدر باز کنید تا به بزرگی دره گرند کنیون برسد. اما ممکن است با استفاده از نسخه‌ای اصلاح شده، از روش شبیه‌سازی ویلیامز- که مرحله کلیدی را بارها تکرار می‌کند و با هر بار تکرار کردن اندکی حافظه (فضا) صرفه جویی می‌کند- به آن دست یافت. این عمل مانند این است که بتوانید طول اهرم خود را به صورت پیاپی افزایش دهید – اگر به اندازه کافی بلندش کنید، می‌توانید هر چیزی را باز کنید. نسخه فعلی الگوریتم فعلا با این نوع ارتقای پیاپی سازگار نیست؛ پژوهشگران نیز نمی‌دانند که این محدودیت، بنیادی است یا خیر. والیانت گفت:" این ممکن است یک گلوگاه نهایی باشد، یا ممکن است در هفته آینده، شخصی آن را حل کند." اگر این مسئله در هفته آینده حل شود ویلیامز حسابی خودش را سرزنش خواهد کرد. او پیش از انتشار مقاله‌اش، ماه‌ها وقت صرف کرد تا نتیجه‌اش را گسترش دهد اما موفق نشد. با این حال، حتی اگر چنین گسترشی امکان پذیر نباشد، ویلیامز مطمئن است که کاوش بیشتر در حوزه حافظه (زمان) قطعا نتایج جالبی را به همراه خواهد داشت. – شاید حتی به پیشرفتی در مسئله‌ای کاملا متفاوت بی‌ا‌نجامد. او گفت:" من هیچ وقت نتوانستم دقیقا آنچه را که می‌خواهم ثابت کنم، اما اغلب چیزی را ثابت می‌کنم که خیلی بهتر از آن چیزی‌ست که در ذهن داشتم."

مترجم : سونیا پورعباس
منبع