Новое доказательство Значительно сокращает пространство, необходимое для вычислений

Удивительная новая работа опровергает 50-летние предположения о компромиссах между вычислительным пространством и временем

Макса Спрингера под редакцией Сары Левин Фрейзер

Присоединяйтесь к нашему сообществу любителей науки!

Подпишитесь на нашу бесплатную ежедневную рассылку новостейВведите свой адрес электронной почтыЯ согласен с тем, что моя информация будет обрабатываться в соответствии с Политикой конфиденциальности Scientific American и Springer Nature Limited.Зарегистрируйтесь

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

Это исследование лежит в основе вычислительной сложности, измеряя пределы того, какие проблемы могут быть решены и с какими затратами во времени и пространстве. В течение почти 50 лет теоретики полагали, что если решение задачи требует t шагов, то для этого также должно потребоваться примерно t бит памяти — те самые 0 и 1, которые машина использует для записи информации. (Технически, это уравнение было t/log(t), но для задействованных чисел log(t) обычно пренебрежимо мало.) Например, если задача состоит из 100 шагов, вам потребуется как минимум 100 битов, что достаточно для тщательного ведения журнала каждого шага. Считалось, что использование меньшего количества разделов требует большего количества шагов — например, расположить книги в алфавитном порядке, переставляя их одну за другой на полке, вместо того чтобы вытаскивать их все и переставлять на место. Но в ходе удивительного открытия, описанного на этой неделе на симпозиуме ACM по теории вычислений в Праге, специалист по информатике из Массачусетского технологического института Райан Уильямс обнаружил, что для решения любой задачи за время t требуется всего около t бит памяти: 100-шаговое вычисление может быть сжато и решено с использованием чего-то порядка 10 бит. «Этот результат показывает, что предыдущая интуиция полностью ложна», — говорит Уильямс. «Я подумал, что, должно быть, что-то не так [с доказательством], потому что это чрезвычайно неожиданно.»

Прорыв основан на «сокращении, — средство преобразования одной задачи в другую, которая может показаться несвязанной, но математически эквивалентной. При сокращении расходов упаковка чемодана влияет на определение месячного бюджета: размер вашего чемодана соответствует вашему общему бюджету, предметы одежды соответствуют потенциальным расходам, а тщательный выбор подходящей одежды — это то же самое, что распределение бюджета. Решение одной проблемы напрямую приведет к решению другой. Эта идея лежит в основе результата Уильямса: любую проблему можно преобразовать в проблему, которую вы можете решить, умело используя пространство, умело втиснув необходимую информацию в число битов, равное квадратному корню. Таким образом, первоначальная проблема должна быть решена с помощью этого компактного контейнера.

О поддержке научной журналистики

Если вам понравилась эта статья, подумайте о том, чтобы поддержать нашу журналистику, отмеченную наградами, подписавшись на нее. Приобретая подписку, вы помогаете обеспечить будущее впечатляющих историй об открытиях и идеях, формирующих наш современный мир.

«Этот прогресс невероятен», — говорит Махди Черагчи, специалист по информатике из Мичиганского университета. «До этого результата были проблемы, которые можно было решить за определенное время, но многие думали, что это невозможно сделать за такое короткое время». Открытие Уильямса, добавляет он, является «шагом в правильном направлении, который мы не знали, как это сделать.»

В то время как компьютеры продолжали сокращаться, наше теоретическое понимание их эффективности резко возросло, что говорит о том, что реальное ограничение заключается не в объеме памяти у нас есть, но насколько мудро мы это используем.

Читать полностью на источнике