No es difícil mostrar que ordenar una matriz de números es difícil para . Si la entrada es una matriz de 1s y 0s, entonces es esencialmente la función C o u n t (dados n bits, genera el número de 1s en binario) ya que C o u n t está completo para T C 0 y es posible para convertir números unarios en números binarios y (logarítmicamente) pequeños números binarios en números unarios en A C :
S o r t ( → x ) = U n a r y ( C o u n t ( → x
Entonces el poder de es esencialmente ordenar una cadena binaria (por ejemplo, 100011 a 000111). Esto es cierto más generalmente cuando los números en la matriz están delimitados. Mi pregunta es ¿qué pasa si los números no están acotados?
¿El problema de ordenar una matriz de números sin límites todavía está en ? ¿Está completo para una clase más grande como N C 1 ?
Respuestas:
Supongamos que tiene números x 1 , ... , x n de ancho m ≥ log n . Sin pérdida de generalidad, todos los números son diferentes (agregue un registro adicional n bits de orden inferior). Se pueden comparar dos números en AC 0 , por lo que en AC 0 podemos calcular, para cada x i , un vector binario v , definido por v j = 1 si x j ≥ x i . En TC 0 podemos ordenar v wnorte X1, ... , xnorte m ≥ lognorte Iniciar sesiónnorte Xyo v vj= 1 Xj≥ xyo v aw , y luego ubique (en AC 0 ) la posición tal que w k = 1 mientras w k - 1 = 0 (donde w 0 = 0 , w n + 1 = 1 ). Dados estos valores k para cada i ∈ [ n ] , podemos calcular la matriz ordenada en AC 0 . En total, obtenemos un circuito TC 0 .k wk= 1 wk - 1= 0 w0 0= 0 wn + 1= 1 k i ∈ [ n ]
fuente