یک دیسک پرِ قرضی رایانه‌ها را سریع‌تر می‌کند
برخی مسائل از نظر زمان ارزان‌اند اما حافظهٔ زیادی می‌طلبند، و برخی برعکس. برای چند کار بنیادی، نظریه‌پردازان محدودیت‌های سختی بر این بده‌بستان اثبات کرده‌اند: با یک حافظهٔ کاری کوچک، نمی‌توانید سریع باشید. مقاله‌ای تازه نشان می‌دهد که منبعی عجیب، یعنی حافظه‌ای که از پیش پر است و باید دست‌نخورده بازگردانده شود، این محدودیت‌ها را می‌شکند.
هارد دیسک قرضی
این مدل محاسبهٔ کاتالیزوری (catalytic computing) نام دارد و در 2014 توسط بورمان، کلیو، کوتسکی، لوف و اسپیلمن معرفی شد. یک الگوریتم حافظه‌ای تمیز و بسیار کوچک، در مرتبهٔ log n بیت برای ورودی‌ای به اندازهٔ n، دریافت می‌کند، به‌علاوهٔ حافظه‌ای کثیف و عظیم که از پیش با داده‌هایی دلخواه پر شده که خودش انتخاب نکرده است. می‌تواند هر طور که بخواهد از هر دو استفاده کند، اما وقتی متوقف می‌شود، هر بیت حافظهٔ کثیف باید دقیقاً همان‌طور که بود باشد.
نویسندگان از تصویر رایج استفاده می‌کنند: هارد دیسک عظیم یک دوست را، پر از خاطرات دیجیتال گران‌بها، قرض می‌گیرید تا محاسبه‌ای انجام دهید. نمی‌خواهید دوستتان را از دست بدهید، پس وقتی کارتان تمام شد هر بیت را بازمی‌گردانید.
این مدل در ابتدا برای اثبات بی‌فایده بودن چنین حافظه‌ای طراحی شده بود. به‌طور شهودی، برای بازگرداندن همه چیز باید همهٔ اطلاعات را نگه دارید، پس هرگز جایی آزاد نمی‌کنید. در کمال شگفتی، عکس آن درست از آب درآمد: حافظهٔ پر امکان حل مسائلی را می‌دهد که هیچ‌کس نمی‌داند چگونه فقط با حافظهٔ تمیز حلشان کند. اما آن نتایج دربارهٔ فضا (حافظه) بودند و الگوریتم‌ها بسیار کند بودند.
سریع‌تر از آنچه به‌طور اثبات‌شده ممکن است
آدلمو موریسون اوروزکو، ناتان شفیلد و رایان ویلیامز (MIT) اکنون به سرعت نگاه می‌کنند. با حافظهٔ تمیز لگاریتمی و مقداری چندجمله‌ای از حافظهٔ قرضی، الگوریتم‌هایی ارائه می‌دهند که:
- یک فهرست را مرتب می‌کنند و یک تبدیل فوریهٔ گسسته را محاسبه می‌کنند، در زمان n^(1+o(1))، یعنی تقریباً خطی؛
- ماتریس‌ها را ضرب می‌کنند، در زمان n^(ω+o(1))، به همان سرعت بهترین روش شناخته‌شده با حافظهٔ نامحدود.
بدون دیسک قرضی، اثبات شده است که حاصل‌ضرب زمان و حافظه باید دست‌کم از مرتبهٔ n² برای مرتب‌سازی و تبدیل فوریه، و n³ برای ضرب ماتریس باشد. پس این الگوریتم‌های کاتالیزوری به سرعت‌هایی می‌رسند که هیچ الگوریتم کم‌حافظهٔ معمولی نمی‌تواند به آن‌ها برسد. نویسندگان آن را نخستین نمایش بی‌قیدوشرط برتری الگوریتم‌های کاتالیزوری بر همتایان غیرکاتالیزوری‌شان می‌نامند.
تغییر بده، بخوان، برگردان
جزء کلیدی، ترفند ترکیبیاتی کوتاهی است. فرض کنید الگوریتمی بتواند بخشی از حافظهٔ قرضی را میان مقداری ناشناخته τ و τ + x جابه‌جا کند، که x نتیجه‌ای است که برایش مهم است. در یک جدول «کمکی» بزرگ، که آن هم قرضی است، به مجموعه‌ای از درایه‌ها که با دقت انتخاب شده‌اند 1 اضافه کنید. درایهٔ واقع در موقعیت τ اگر و تنها اگر x به مجموعهٔ معینی تعلق داشته باشد یک واحد بالا می‌رود. سپس همهٔ گام‌ها را وارونه اجرا کنید؛ دیسک مثل قبل می‌شود، جز بیتی از پاسخ که می‌خواستید.
روی هم چیدن این ترفند لایه به لایه، مدارهای کم‌عمق را به‌سرعت ارزیابی می‌کند. سپس نویسندگان شبکه‌های مرتب‌سازی، تبدیل‌های فوریهٔ سریع و ضرب سریع ماتریس را به شکل چنین مدارهایی بازنویسی می‌کنند. در محاسبات حسابی، تنها لایه‌هایی که دو مجهول را در هم ضرب می‌کنند هزینهٔ اضافی دارند؛ لایه‌های صرفاً خطی تقریباً رایگان‌اند.
مقایسه‌ای منصفانه
یک اعتراض: محدودیت‌های کلاسیک فرض می‌کنند که پاسخ یک بار، از چپ به راست، روی یک نوار خروجی جداگانه نوشته می‌شود، در حالی که الگوریتم‌های کاتالیزوری پاسخشان را روی دیسک قرضی می‌نویسند. مقاله به این موضوع می‌پردازد. نویسندگان نشان می‌دهند که الگوریتم‌هایشان می‌توانند پاسخ را در دو گذر روی یک نوار خروجی بنویسند، و اینکه برای الگوریتم‌های معمولی دو گذر بیش از یک گذر کمکی نمی‌کند. بنابراین محدودیت‌ها همچنان برقرارند و جدایی پابرجاست. آن‌ها همچنین اثبات می‌کنند که حتی با دیسک قرضی، یک گذر کافی نیست: در آن صورت مرتب‌سازی به همان سد n² برمی‌خورد.
فهرستی بلند از بهره‌مندان
همین ابزارها الگوریتم‌های کاتالیزوری سریعی برای ضرب اعداد صحیح بزرگ و چندجمله‌ای‌ها، شمارش مثلث‌ها و یافتن خوشه‌ها (clique) در شبکه‌ها، تشخیص مسیرها و دورها، و تطبیق الگوهای متنی با نویسه‌های عام (wildcard) به دست می‌دهند. زمان اجرای آن‌ها، تا ضرایبی کوچک، با بهترین الگوریتم‌های شناخته‌شده‌ای که هر قدر بخواهند حافظه دارند برابر است. در هر مورد، حافظهٔ قرضی باید دقیقاً همان‌طور که امانت داده شده بود بازگردد.