O que é mais difícil: embaralhar um baralho classificado ou ordenar um baralhado?

Você tem uma matriz de elementos distintos. Você tem acesso a um comparador (a função de caixa preta tomando dois elementos e e retornando verdadeira sse ) e uma fonte verdadeiramente aleatório de bits (a função de caixa preta que não recebe argumentos e retornar um pouco independentemente uniformemente aleatório). Considere as duas tarefas a seguir:$n$$a$$b$$a < b$

1. A matriz está atualmente classificada. Produza uma permutação selecionada de maneira uniforme (ou aproximadamente uniforme).
2. A matriz consiste em alguma permutação selecionada uniformemente aleatoriamente por natureza. Produza uma matriz classificada.

Minha pergunta é

Qual tarefa requer mais energia assintoticamente?

Não consigo definir a pergunta com mais precisão porque não sei o suficiente sobre a conexão entre teoria da informação, termodinâmica ou qualquer outra coisa necessária para responder a essa pergunta. No entanto, acho que a pergunta pode ser bem definida (e espero que alguém me ajude com isso em uma resposta!).

Agora, algoritmicamente, minha intuição é que eles são iguais. Observe que todo tipo é um shuffle ao contrário e vice-versa. A classificação requer comparações, enquanto embaralha, pois seleciona uma permutação aleatória deopções, requer bits aleatórios. O embaralhamento e a classificação exigem cerca de trocas.$\log n! \approx n \log n$$n!$$\log n! \approx n \log n$$n$

No entanto, acho que deveria haver uma resposta aplicando o princípio de Landauer , que diz que é preciso energia para "apagar" um pouco. Intuitivamente, acho que isso significa que classificar a matriz é mais difícil, porque requer "apagar" bits de informação, passando de um estado fundamental de desordem de baixa energia e alta entropia para um estado altamente ordenado. Mas, por outro lado, para qualquer cálculo dado, a classificação apenas transforma uma permutação em outra. Como sou um completo não especialista aqui, esperava que alguém com conhecimento da conexão com a física pudesse ajudar a "resolver" isso!$n \log n$

(A pergunta não obteve respostas em math.se , por isso estou republicando aqui. Espero que esteja tudo bem.)

$n$$log n! \approx n \log_2 n$$(n \ln n) k T$$n \log_2 n$

Observe que esses são apenas limites inferiores teóricos. A energia atualmente consumida por esses processos em um computador digital real não tem relação com a análise acima.

Nem. Qualquer circuito pode ser reversível , mantendo o controle da entrada, e a dissipação de energia da computação reversível pode ser arbitrariamente pequena .