Entropie und rechnerische Komplexität

Es gibt Forscher, die zeigen, dass das Löschen von Bits Energie verbrauchen muss. Gibt es jetzt Forschungen zum durchschnittlichen Energieverbrauch von Algorithmen mit der Rechenkomplexität ? Ich vermute, die Komplexität von hängt mit dem durchschnittlichen Energieverbrauch zusammen. Ich hoffe, ich kann hier eine Antwort finden.$F(n)$$F(n)$

Ja, aber der größte Teil der bisherigen Arbeit (mit Ausnahme der jüngsten, siehe unten) konzentrierte sich darauf, irreversible Berechnungen in reversible umzuwandeln, um so eine Entropieerzeugung zu vermeiden. (Hinweis: Es gibt einen wichtigen Unterschied zwischen der Energie, die für einen Berechnungslauf benötigt wird, und der Entropie, die durch die Berechnung erzeugt und an die Umgebung abgegeben wird, normalerweise in Form von Wärme.)

$kT \ln(2)$

• Bennett, Zeit / Raum-Kompromisse für die reversible Berechnung . SICOMP 1989

• Levine & Sherman. Eine Anmerkung zu Bennetts Time-Space-Kompromiss für die reversible Berechnung . SICOMP 1990.

• Li & Vitanyi. Reversible Simulation der irreversiblen Berechnung . CCC 1996

• Lange, McKenzie und Tapp. Reversibler Raum entspricht deterministischem Raum . JCSS 2000.

In jüngerer Zeit

Demaine, Lynch, Mirano und Tyagi. Energieeffiziente Algorithmen , 2016.

studierte teilweise reversible Algorithmen - das heißt, wenn Sie bereit sind, etwas Entropie zu zahlen, kann man für standardmäßige algorithmische Aufgaben die oben erwähnten allgemeinen irreversiblen zu reversiblen Simulationen verbessern. Reversible Computing beschäftigt eine ganze Forschungsgemeinschaft, nämlich. die Reversible Computing- Konferenz, die bereits im zehnten Jahr stattfindet.

$\ln(2)$

Kolchinsky & Wolpert, Abhängigkeit der Dissipation von der Anfangsverteilung über Zustände . J. Stat. Mech. 2017 ( arXiv link )

(und Referenzen darin).

Wir haben im August 2017 im Santa Fe Institute einen Workshop zu diesem Thema veranstaltet (in dem Sie die Namen einiger Forscher und relevante Vortragstitel sehen können), der eine ganze Reihe neuer Fragen sowohl in Bezug auf die Physik als auch auf die Komplexität der thermodynamischen Berechnungen aufwirft.