Алгоритмы: память важнее времени
В июле 2024 года Райан Уильямс, теоретик компьютерных наук из MIT, обнаружил нечто невероятное. Его доказательство показало, что память в вычислениях гораздо мощнее, чем считалось раньше: даже небольшой объем памяти может компенсировать значительное увеличение времени выполнения алгоритма. Это противоречило общепринятым представлениям, и сам Уильямс поначалу не поверил себе.
В 1975 году Джон Хопкрофт, Вольфганг Пауль и Лесли Валиант доказали, что пространство (память) немного эффективнее времени в вычислениях. Но затем прогресс остановился. Ученые считали, что улучшить этот результат невозможно — пока не появился Уильямс.
Его подход основан на идее «сжимаемых камешков» — методе, который позволяет алгоритмам использовать память более эффективно, чем предполагалось. Это не просто небольшое улучшение, а настоящий прорыв: теперь можно преобразовать любой алгоритм так, чтобы он требовал гораздо меньше памяти, пусть и за счет увеличения времени работы.
Почему это важно?
Результат Уильямса имеет два ключевых следствия:
- Позитивное: алгоритмы с малым объемом памяти могут решать задачи, которые раньше требовали больше времени.
- Негативное: некоторые задачи принципиально нельзя решить быстро, если не хватает памяти.
Это приближает нас к решению одной из главных проблем теоретической информатики — вопроса о соотношении классов сложности P и PSPACE. Пока что разрыв между ними огромен, но теперь появился инструмент, который может помочь его преодолеть.
Что дальше?
Сам Уильямс сомневается, что его метод можно масштабировать до уровня P vs PSPACE. Но даже если нет — это уже огромный шаг вперед. Как сказал Валиант: «Если ты получаешь математический результат, который становится лучшим за 50 лет, ты явно делаешь что-то правильно».
Остается только ждать, кто подхватит эту идею и доведет ее до логического завершения. Может, это случится через 50 лет. А может — на следующей неделе.
