Энтропия и вычислительная сложность

Есть исследователь, показывающий, что стирающий бит должен потреблять энергию, а сейчас проводится какое-либо исследование среднего потребления энергии алгоритмом с вычислительной сложностью ? Я предполагаю, что вычислительная сложность F ( n ) коррелирует со средним потреблением энергии, надеюсь, я смогу получить ответ здесь.$F(n)$$F(n)$

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

$kT \ln(2)$

• Беннетт, Компромиссы времени / пространства для обратимых вычислений . SICOMP 1989

• Левин и Шерман. Замечание о пространственно-временном компромиссе Беннетта для обратимых вычислений . SICOMP 1990.

• Ли & Витаньи. Обратимое моделирование необратимых вычислений . CCC 1996

• Ланге, Маккензи и Тапп. Обратимое пространство равно детерминированному пространству . ССП 2000.

В последнее время,

Демейн, Линч, Мирано и Тяги. Энергоэффективные алгоритмы , 2016.

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

$\ln(2)$

Колчинский, Вольперт, Зависимость диссипации от начального распределения по состояниям . J. Stat. Мех. 2017 ( ссылка на arXiv )

(и ссылки в нем).

Мы провели семинар по этому вопросу в Институте Санта-Фе в августе 2017 года (где вы можете увидеть имена некоторых исследователей и названия выступлений), и он поднимает совершенно новый набор вопросов как по физике, так и по термодинамическим вычислительным сложностям.