Complejidad de clasificación

8

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 CTC0CountnCountTC0 :AC0

S o r t ( x ) = U n a r y ( C o u n t ( xCotunortet(X)=siyonorteunary(Sort(X))
Sort(x)=Unary(Count(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?TC0

¿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 ?TC0NC1

Kaveh
fuente
Por cierto, si conoce una referencia para "ordenar matrices de bits es -completa", hágamelo saber. TC0
Kaveh
¿Revisaste Cook & Nguyen?
Yuval Filmus
2
@Kaveh, la reducción está en Chandra, Stockmeyer y Vishkin, "Reducibilidad de profundidad constante", SIAM J. Comput. 13 (2), 1984.
Jan Johannsen

Respuestas:

9

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 jx i . En TC 0 podemos ordenar v wnx1,,xnmlognIniciar sesiónnorteXyovvj=1XjXyov 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 .kwk=1wk-1=0 0w0 0=0 0wnorte+1=1kyo[norte]

Yuval Filmus
fuente
buen truco :) (cuenta el número de números más pequeños en la matriz), gracias Yuval.
Kaveh