Будь-яке обчислення можна повторити, маючи корінь із його пам'яті

Кожне обчислення витрачає дві речі: час, тобто кількість кроків, і пам’ять, тобто простір, де воно тримає свою чернетку. Нам здається, що ці двоє пов’язані: якщо задача працює довго, то й чернетки за дорогу назбирується чимало. Пів століття математика наче це підтверджувала. Найкраще, що вдавалося довести, — що довге обчислення можна повторити, майже не заощадивши пам’яті, хіба зрізати тоненьку смужку.

2025 року Раян Вільямс довів дещо набагато дивніше, і це був перший справжній зсув у цьому питанні за пів століття. Візьми будь-яке обчислення, хоч яке довге. Його завжди можна повторити, маючи приблизно квадратний корінь із тієї пам’яті, яка наче була потрібна. Пробіг на мільйон кроків, що ніби потребував мільйона комірок чернетки, можна переграти десь у тисячі. Трильйон кроків стискається до якогось мільйона. Що довше обчислення, то безглуздіше виглядає ця економія.

Ось що я все обертаю в думках. Це не означає, що твоєму ноутбуку від завтра треба менше пам’яті. Це доказ, що таке скорочення можливе завжди, а не програма, яку можна звідкись завантажити; і фокус має ціну в часі: ти викидаєш проміжні результати й рахуєш їх наново, щойно вони знову знадобляться, виміняючи пам’ять, якої немає, на час, який є. Та сам факт, що так можна, переписує те, що ми наче розуміли. Пам’ять, виявляється, набагато дешевша за час. Майже все, що ти здатен обчислити, можна обчислити в наперстку простору — якщо ти згоден переробляти роботу.

Це ще й маленька тріщина в одній з найдавніших стін цієї науки: чи справді час і пам’ять — різні за суттю ресурси. Стіни вона не валить. Але пів століття та стіна не зрушувала ні на крок, а тепер зрушила — на квадратний корінь. І найдужче мене бере те, як довго очевидне стояло без сумніву. Усі відчували, що пам’ятати й переробляти — чесний обмін. Знадобилося пів століття й один доказ, щоб дізнатися, наскільки той обмін насправді нерівний.