Entropia i złożoność obliczeniowa

Są badacze wykazujący, że bit wymazywania musi zużywać energię, czy teraz są jakieś badania dotyczące średniego zużycia energii algorytmu o złożoności obliczeniowej ? Wydaje mi się, że złożoność obliczeniowa F ( n ) jest skorelowana ze średnim zużyciem energii, mam nadzieję, że mogę tu znaleźć odpowiedź.$F(n)$$F(n)$

Tak, ale większość dotychczasowych prac (z wyjątkiem bardzo niedawnych, patrz poniżej) koncentrowała się na przekształceniu obliczeń nieodwracalnych w odwracalne, mając nadzieję na uniknięcie generowania entropii. (Uwaga: istnieje istotna różnica między energią potrzebną do uruchomienia obliczeń a entropią wygenerowaną przez obliczenia i wypuszczoną do środowiska, zwykle w postaci ciepła).

$kT \ln(2)$

• Bennett, Kompromisy czasowo-kosmiczne dla obliczeń odwracalnych . SICOMP 1989

• Levine & Sherman. Uwaga na temat kompromisu czasoprzestrzennego Bennetta w zakresie obliczeń odwracalnych . SICOMP 1990.

• Li & Vitanyi. Odwracalna symulacja obliczeń nieodwracalnych . CCC 1996

• Lange, McKenzie i Tapp. Przestrzeń odwracalna równa się przestrzeni deterministycznej . JCSS 2000.

Niedawno,

Demaine, Lynch, Mirano i Tyagi. Algorytmy energooszczędne , 2016.

studiował częściowo odwracalne algorytmy - to znaczy, jeśli jesteś skłonny zapłacić trochę entropii, dla standardowych zadań algorytmicznych można poprawić ogólne symulacje nieodwracalne do odwracalnych wspomniane powyżej. Komputery odwracalne poświęcone są całej społeczności naukowców, a mianowicie. odwracalny Computing Conference, teraz w jej 10 lat.

$\ln(2)$

Kolchinsky & Wolpert, Zależność rozproszenia od początkowego rozkładu między państwami . J. Stat. Mech 2017 ( link arXiv )

(i odnośniki tam zawarte).

W sierpniu 2017 r. Gościliśmy warsztaty na ten temat w Instytucie w Santa Fe (gdzie można zobaczyć nazwiska niektórych badaczy i tytuły ważnych rozmów), co rodzi zupełnie nowy zestaw pytań zarówno w zakresie fizyki, jak i termodynamicznej złożoności obliczeniowej.