Entropia e complexidade computacional

12

Existem pesquisadores mostrando que o apagamento de bit deve consumir energia, agora existem pesquisas sobre o consumo médio de energia do algoritmo com complexidade computacional ? Eu acho que a complexidade computacional F ( n ) está correlacionada com o consumo médio de energia, espero poder obter alguma resposta aqui.F(n)F(n)

cc.complexity-theory reference-request it.information-theory quantum-information statistical-physics XL _At_Here_There
fonte
Vincular ao artigo em questão melhoraria essa questão.
Stella Biderman
@StellaBiderman obrigado, mas não encontrei nenhum link no seu comentário.
XL _At_Here_There
Não sei de que artigo / pesquisador você está falando. Eu estou sugerindo que você fornecer I
Stella Biderman
1
@StellaBiderman Entendi mal seus comentários, na verdade, acabei de ler um texto constatando que "o bit de apagamento precisa consumir energia" na complexidade de Kolmogorov e sua aplicação por Viatanyi e Li. Eu acho que eu não li todos os outros artigos e livros relacionados
XL _At_Here_There

Respostas:

16

Sim, mas a maior parte do trabalho até agora (exceto muito recentemente, veja abaixo) se concentrou em transformar cálculos irreversíveis em reversíveis, esperando assim evitar qualquer geração de entropia. (Nota: existe uma diferença importante entre a energia necessária para executar uma computação e a entropia gerada pela computação e lançada no ambiente, geralmente na forma de calor.)

kTln⁡(2)

Mais recentemente,

Demaine, Lynch, Mirano e Tyagi. Algoritmos de eficiência energética , 2016.

estudados algoritmos parcialmente reversíveis - ou seja, se você estiver disposto a pagar alguma entropia, para tarefas algorítmicas padrão, pode-se melhorar as simulações gerais irreversíveis para reversíveis mencionadas acima. A computação reversível tem uma comunidade inteira de pesquisadores dedicados a ela, viz. a conferência de computação reversível , agora em seu 10º ano.

ln⁡(2)

Kolchinsky & Wolpert, Dependência de dissipação na distribuição inicial dos estados . J. Stat. Mech. 2017 ( link arXiv )

(e referências).

Organizamos um workshop sobre isso no Instituto Santa Fe em agosto de 2017 (onde você pode ver os nomes de alguns pesquisadores e falar de títulos relevantes), e isso levanta um novo conjunto de questões tanto na física quanto na complexidade computacional termodinâmica.

Joshua Grochow
fonte
A Máquina de Turing ou a Tese de Church-Turing podem ser governadas ou restritas pela lei física, de modo que a possibilidade de implementação da computação quântica ou da comunicação quântica pode ser deduzida da lei da física, como a segunda lei da mecânica estatística, a relatividade geral. Então eu acho que se houver qualquer resultado sobre a ligação da lei tese e física
XL _At_Here_There
E parece que o site de física não está interessado nos tópicos desse tipo.
XL _At_Here_There
@XL_at_China: Existe uma "tese da Igreja Física de Turing", mas isso tem pouco a ver com a segunda lei, uma vez que tanto a tese da Igreja-Turing quanto sua versão física são exatamente o que é computável, não qualquer tipo de estimativa quantitativa , mas a segunda lei é uma afirmação quantitativa. Além disso, embora ainda não tenha havido uma tonelada de publicações, em nosso workshop os físicos definitivamente pareciam interessados.
Joshua Grochow
Eu tentara encontrar o vínculo há vários anos, mas não obtive nenhum resultado. Intuitivamente, a computabilidade parece ter que estar ligada à segunda lei termodinâmica. E considerando a Máquina de Turing no termo da relatividade geral, o problema se torna interessante. Mas não sei se há físicos interessados ​​em esse problema.
XL _At_Here_There
E poderíamos postar uma pergunta relacionada à física do site e discuti-la com o físico?
XL _At_Here_There