Complexidade da classificação

8

Não é difícil mostrar que classificar uma matriz de números é difícil para . Se a entrada é uma matriz de 1s e 0s então é essencialmente a função C o u n t (dado n bits de saída do número de 1s em binário) desde C S u n t é completo para o t C 0 e é possível converter números unários em números binários e (logarítmica) pequenos números binários em números unários em A C 0 :TC0CountnCountTC0AC0

S o r t ( x ) = L n uma r y ( C o u n t ( x ) )Count(x)=Binary(Sort(x))
Sort(x)=Unary(Count(x))

Portanto, o poder de é essencialmente classificar uma sequência binária (por exemplo, 100011 a 000111). Isso ocorre mais geralmente quando os números na matriz são limitados. Minha pergunta é: e se os números não forem limitados?TC0

O problema de classificar uma matriz de números ilimitados ainda está em ? Está completo para uma classe maior como N C 1 ?TC0NC1

Kaveh
fonte
Btw, se você souber uma referência para "classificar matrizes de bits é -complete", por favor me avise. TC0
Kaveh
Você verificou Cook & Nguyen?
Yuval Filmus
2
@ Kaveh, a redução está em Chandra, Stockmeyer e Vishkin, "Constant Depth Reducibility", SIAM J. Comput. 13 (2), 1984.
Jan Johannsen

Respostas:

9

Suponha que você tenha números x 1 , , x n de largura m log n . Sem perda de generalidade, todos os números são diferentes (adicione um log extra n bits de ordem inferior). Dois números podem ser comparados em AC 0 , portanto, em AC 0 , podemos calcular, para cada x i , um vetor binário v , definido por v j = 1 se x jx i . No TC 0 , podemos ordenar v paranx1,,xnmregistronregistronxEuvvj=1xjxEuv , em seguida, localize (em AC0) a posição k tal que w k = 1 enquanto w k - 1 = 0 (onde w 0 = 0 , w n + 1 = 1 ). Dados esses valores k para cada i [ n ] , podemos calcular a matriz classificada em AC0. No total, obtemos umcircuitoTC0.WkWk=1Wk-1=0 0W0 0=0 0Wn+1=1kEu[n]

Yuval Filmus
fonte
belo truque :) (conte o número de números menores na matriz), obrigado Yuval.
Kaveh