¿Qué es más difícil: barajar un mazo ordenado o ordenar uno barajado?

Tiene una matriz de elementos distintos. Tiene acceso a un comparador (una función de la caja negro teniendo dos elementos un y b y devolver verdadero si y sólo si un < b ) y una fuente verdaderamente aleatoria de bits (una función de la caja negro sin argumentos y devolver un poco independientemente uniformemente aleatorio). Considere las siguientes dos tareas:$n$$a$$b$$a < b$

1. La matriz está actualmente ordenada. Produzca una permutación seleccionada al azar de manera uniforme (o aproximadamente uniforme).
2. La matriz consiste en alguna permutación seleccionada uniformemente al azar por naturaleza. Produce una matriz ordenada.

Mi pregunta es

¿Qué tarea requiere más energía asintóticamente?

No puedo definir la pregunta con mayor precisión porque no sé lo suficiente sobre la conexión entre la teoría de la información, la termodinámica o cualquier otra cosa necesaria para responder a esta pregunta. Sin embargo, creo que la pregunta se puede definir bien (¡y espero que alguien me ayude con esto en una respuesta!).

Ahora, algorítmicamente, mi intuición es que son iguales. Tenga en cuenta que cada tipo es una mezcla aleatoria a la inversa, y viceversa. La clasificación requiere comparaciones, mientras baraja, ya que selecciona una permutación aleatoria de n ! opciones, requiere log n ! ≈ n log n bits aleatorios. Tanto la mezcla como la clasificación requieren aproximadamente n intercambios.$\log n! \approx n \log n$$n!$$\log n! \approx n \log n$$n$

Sin embargo, siento que debería haber una respuesta aplicando el principio de Landauer , que dice que requiere energía para "borrar" un poco. Intuitivamente, creo que esto significa que la clasificación de la matriz es más difícil, ya que requiere "borrar" bits de información, al pasar de un bajo consumo de energía, el estado de alta entropía suelo del trastorno a un altamente ordenada uno. Pero, por otro lado, para cualquier cálculo dado, la clasificación simplemente transforma una permutación en otra. Como soy un completo no experto aquí, ¡esperaba que alguien con conocimiento de la conexión con la física pudiera ayudar a "resolver" esto!$n \log n$

(La pregunta no obtuvo ninguna respuesta en math.se , así que la vuelvo a publicar aquí. Espero que esté bien).

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

Tenga en cuenta que estos son solo límites inferiores teóricos. La energía actualmente consumida por estos procesos en una computadora digital real no guarda relación con el análisis anterior.

Ninguno. Cualquier circuito puede hacerse reversible manteniendo un registro de la entrada, y la disipación de energía del cálculo reversible puede hacerse arbitrariamente pequeña .