Для алгоритмов небольшая память важнее большого времени.

Профессор компьютерных наук Массачусетского технологического института (MIT) Райан Уильямс (Ryan Williams) предположил, что небольшого объема памяти "было бы столь же полезно, как и большого количества времени во всех мыслимых вычислениях", пишет Quanta Magazine.

В феврале он наконец опубликовал свое доказательство в интернете, что вызвало широкое признание.

Каждый алгоритм требует определенного времени для выполнения и определенного пространства для хранения данных во время работы. До сих пор все известные алгоритмы для решения определенных задач требовали объема памяти, примерно пропорционального времени их выполнения, и исследователи долгое время полагали, что добиться лучшего результата невозможно. Доказательство Уильямса установило математическую процедуру для преобразования любого алгоритма – независимо от его назначения – в форму, использующую гораздо меньше памяти.

Более того, этот результат – утверждение о том, что можно вычислить при определенном объеме памяти – также подразумевает второй результат, о том, что нельзя вычислить за определенное время. Сам по себе этот второй результат не является неожиданным: исследователи ожидали, что он верен, но не имели представления о том, как его доказать. Решение Уильямса, основанное на его всеобъемлющем первом результате, кажется почти карикатурно избыточным, подобно доказательству вины подозреваемого убийцы путем установления железного алиби для всех остальных людей на планете. Оно также может предложить новый способ атаки одной из старейших нерешенных проблем в информатике.

"Это потрясающий результат и огромный шаг вперед", – сказал Пол Биме (Paul Beame), ученый-компьютерщик из Вашингтонского университета.