Komplexität der Sortierung

8

Es ist nicht schwer zu zeigen, dass das Sortieren eines Arrays von Zahlen für schwierig ist . Wenn die Eingabe ein Array von 1s und 0s ist, ist es im Wesentlichen die Funktion C o u n t (bei n Bits wird die Anzahl von 1 s binär ausgegeben), da C o u n t für T C 0 vollständig ist und dies möglich ist unäre Zahlen in Binärzahlen und (logarithmisch) kleine Binärzahlen in unäre Zahlen in A C 0 umzuwandelnTC0CountnCountTC0AC0 :

S o r t ( x ) = U n a R y ( C o u n t ( x ) )Count(x)=Binary(Sort(x))
Sort(x)=Unary(Count(x))

Die Potenz von besteht also im Wesentlichen darin, eine binäre Zeichenfolge zu sortieren (z. B. 100011 bis 000111). Dies gilt allgemeiner, wenn die Zahlen im Array begrenzt sind. Meine Frage ist, was ist, wenn die Zahlen nicht begrenzt sind?TC0

Ist das Problem, ein Array unbegrenzter Zahlen zu sortieren, immer noch in ? Ist es für eine größere Klasse wie N C 1 vollständig ?TC0NC1

Kaveh
quelle
Übrigens, wenn Sie eine Referenz für "Sortieren von Arrays von Bits ist vollständig" kennen, lassen Sie es mich bitte wissen. TC0
Kaveh
Haben Sie Cook & Nguyen überprüft?
Yuval Filmus
2
@Kaveh, die Reduktion erfolgt in Chandra, Stockmeyer und Vishkin, "Constant Depth Reducibility", SIAM J. Comput. 13 (2), 1984.
Jan Johannsen

Antworten:

9

nx1,,xnmlognlognxivvj=1xjxivwkwk=1wk1=0w0=0wn+1=1ki[n]

Yuval Filmus
quelle
netter Trick :) (zähle die Anzahl der kleineren Zahlen im Array), danke Yuval.
Kaveh