- 19,406
- 40
- 8 Ноя 2022
То, что считали невозможным с 70-х, внезапно оказалось возможным. Просто никто не смотрел с этой стороны.
Американский теоретик Райан Уильямс (MIT) представил доказательство, которое может изменить представления о фундаментальных ресурсах вычислений — времени и памяти. В своей работе он предложил новый универсальный способ симуляции алгоритмов, который впервые за 50 лет позволил существенно сократить требования к памяти — даже при сохранении полной вычислительной мощности. Его открытие уже называют крупнейшим прорывом в теории вычислительной сложности с 1970-х годов.
Для просмотра ссылки Войдиили Зарегистрируйся Уильямс решил перепроверить набросок идеи, которую ранее посчитал слишком безумной, чтобы быть истиной. Доказательство утверждало, что память может быть настолько же мощным вычислительным ресурсом, как и время: небольшое её количество может заменить огромное количество шагов. После тщательного анализа он не нашёл в доказательстве ошибок.
В феврале 2025 года он Для просмотра ссылки Войдиили Зарегистрируйся , вызвав восторг у коллег. Ави Вигдерсон из Института перспективных исследований (Принстон) написал ему с темой письма «You blew my mind». Пол Бим (Университет Вашингтона) назвал результат «ошеломляющим» и отметил, что не удивлён, что его достиг именно Уильямс.
Ключевой вывод работы — возможность преобразовать любой алгоритм так, чтобы он использовал существенно меньше памяти, пусть и за счёт большего времени выполнения. При этом открытие имеет и второй, не менее важный эффект: из него следует, что некоторые вычисления невозможно выполнить за ограниченное время без увеличения объёма памяти — что было ожидаемо, но до сих пор не имело строгого доказательства.
Уильямс вырос на ферме в Алабаме, впервые увидел компьютер в семь лет и сразу увлёкся программированием. В старших классах он поступил в специализированную школу, где познакомился с теорией сложности — областью, изучающей ресурсы, необходимые для решения задач. Позже, поступив в Корнелл, он учился у одного из основателей теории сложности, Юриса Хартманиса, и именно тот стал его наставником.
Теория сложности изучает классы задач, различающиеся по времени и памяти, например, P (быстро решаемые задачи) и PSPACE (решаемые с ограниченной памятью). До сих пор было неясно, насколько мощнее PSPACE, и можно ли это строго доказать. В 1975 году Хопкрофт, Пауль и Вэлиант предложили универсальную симуляцию, экономящую немного памяти, но дальнейший прогресс застопорился: в 1983 году Пауль с коллегами доказали, что улучшить симуляцию невозможно — при определённых допущениях.
Прорыв произошёл после того, как в 2023 году Джеймс Кук и Ян Мерц нашли способ обойти одно из этих допущений, Для просмотра ссылки Войдиили Зарегистрируйся , использующий «сжимаемые» единицы памяти, как «гибкие камешки». Именно эта идея вдохновила Уильямса.
Он понял, что метод «гибких камешков» можно использовать для создания новой универсальной симуляции, которая сокращает требования к памяти до квадратного корня от исходного времени работы алгоритма. В теории это означает, что пространство действительно мощнее времени. Такой подход может не иметь практического применения из-за роста времени выполнения, но в теоретическом смысле он радикально меняет правила игры.
Лесли Вэлиант, один из авторов классической симуляции, был впечатлён, узнав об открытии от Уильямса в автобусе по пути на работу. «Если у тебя есть результат, лучший за последние 50 лет, ты явно всё делаешь правильно», — сказал он.
Уильямс доказал как положительное утверждение — что небольшое количество памяти может заменить большее количество времени, — так и отрицательное: что при фиксированном времени невозможно решить некоторые задачи без увеличения объёма памяти. Эти результаты ещё не доказывают, что PSPACE больше P, но приближают на шаг к этой цели.
Он надеется, что следующий прорыв может случиться в любую минуту. И хотя сам не смог расширить своё доказательство, он уверен — это только начало. «Я редко доказываю именно то, что хотел, — сказал Уильямс. — Но часто оказывается, что я доказал нечто куда более интересное».
Американский теоретик Райан Уильямс (MIT) представил доказательство, которое может изменить представления о фундаментальных ресурсах вычислений — времени и памяти. В своей работе он предложил новый универсальный способ симуляции алгоритмов, который впервые за 50 лет позволил существенно сократить требования к памяти — даже при сохранении полной вычислительной мощности. Его открытие уже называют крупнейшим прорывом в теории вычислительной сложности с 1970-х годов.
Для просмотра ссылки Войди
В феврале 2025 года он Для просмотра ссылки Войди
Ключевой вывод работы — возможность преобразовать любой алгоритм так, чтобы он использовал существенно меньше памяти, пусть и за счёт большего времени выполнения. При этом открытие имеет и второй, не менее важный эффект: из него следует, что некоторые вычисления невозможно выполнить за ограниченное время без увеличения объёма памяти — что было ожидаемо, но до сих пор не имело строгого доказательства.
Уильямс вырос на ферме в Алабаме, впервые увидел компьютер в семь лет и сразу увлёкся программированием. В старших классах он поступил в специализированную школу, где познакомился с теорией сложности — областью, изучающей ресурсы, необходимые для решения задач. Позже, поступив в Корнелл, он учился у одного из основателей теории сложности, Юриса Хартманиса, и именно тот стал его наставником.
Теория сложности изучает классы задач, различающиеся по времени и памяти, например, P (быстро решаемые задачи) и PSPACE (решаемые с ограниченной памятью). До сих пор было неясно, насколько мощнее PSPACE, и можно ли это строго доказать. В 1975 году Хопкрофт, Пауль и Вэлиант предложили универсальную симуляцию, экономящую немного памяти, но дальнейший прогресс застопорился: в 1983 году Пауль с коллегами доказали, что улучшить симуляцию невозможно — при определённых допущениях.
Прорыв произошёл после того, как в 2023 году Джеймс Кук и Ян Мерц нашли способ обойти одно из этих допущений, Для просмотра ссылки Войди
Он понял, что метод «гибких камешков» можно использовать для создания новой универсальной симуляции, которая сокращает требования к памяти до квадратного корня от исходного времени работы алгоритма. В теории это означает, что пространство действительно мощнее времени. Такой подход может не иметь практического применения из-за роста времени выполнения, но в теоретическом смысле он радикально меняет правила игры.
Лесли Вэлиант, один из авторов классической симуляции, был впечатлён, узнав об открытии от Уильямса в автобусе по пути на работу. «Если у тебя есть результат, лучший за последние 50 лет, ты явно всё делаешь правильно», — сказал он.
Уильямс доказал как положительное утверждение — что небольшое количество памяти может заменить большее количество времени, — так и отрицательное: что при фиксированном времени невозможно решить некоторые задачи без увеличения объёма памяти. Эти результаты ещё не доказывают, что PSPACE больше P, но приближают на шаг к этой цели.
Он надеется, что следующий прорыв может случиться в любую минуту. И хотя сам не смог расширить своё доказательство, он уверен — это только начало. «Я редко доказываю именно то, что хотел, — сказал Уильямс. — Но часто оказывается, что я доказал нечто куда более интересное».
- Источник новости
- www.securitylab.ru
