So speichern Sie eine Permutation kompakt (2022)

--- Titel: So speichern Sie eine Permutation kompakt Breaks: false --- $$ \def\Fp{\mathbb{F}_p} \def\deq{\mathrel{\mathop:}=} \ def \range#1{[{#1}]} \def\alg#1{\textsf{#1}} \def\rank{\textsf{rank}} \def\msb{\textsf{msb}} \ def \bit{\textsf{bit}} \def\mib#1{\color{blue}{\mathbf{{#1}}}} \def\mir#1{\color{red}{\mathbf{{ # 1}}}} $$ # So speichern Sie eine Permutation kompakt ### Bram Cohen und Dan Boneh --- In dieser Anmerkung beschreiben wir eine kompakte Methode zum Speichern einer Permutation und unterstützen gleichzeitig eine schnelle Methode zum Speichern einer Permutation die Permutation umkehren. Diese Frage stellt sich natürlich bei der Optimierung der der Blockchain zugrunde liegenden Software [Chia Proof-of-Space](https://docs.chia.net/docs/03consensus/proof-of-space). [Chia](https://chia.net) ersetzt Nakamotos machthungrigen Proof-of-Work-Konsens durch einen umweltfreundlichen [Proof-of-Space](https://en.wikipedia.org/wiki/Proof_of_space) . Wir beenden die Notiz mit einem offenen Problem, von dem wir nicht wissen, wie wir es lösen können. ## So speichern Sie eine Permutation kompakt Eine Permutation auf der Menge $\range{n} \deq \{0,1,2,\ldots,n-1\}$ ist eine Eins-zu-eins-Funktion von $\range {n }$ zu $\range{n}$. Die Gruppe aller Permutationen $n!$ auf $\range{n}$ wird mit $S_n$ bezeichnet. Hier ist eine Beispielpermutation in $S_{16}$, die $0 \auf 9,\\1 \auf 14,\\2 \auf 12,\\3 \auf 2$ usw. abbildet. : $$ \begin{equation } \pi_1 \deq \left(\begin{array}{*{16}c} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\ 9 & 14 & 12 & 2 & 7 & 10 & 13 & 3 & 1 & 15 & 0 & 6 & 4 & 11 & 5 & 8 \end{array} \right) \ end{equation} \tag{ 1}\label{eq:exmpl} $$ Wir sagen, dass $D$ eine Datenstruktur zum Speichern einer Permutation ist, wenn $D$ die folgende Schnittstelle unterstützt: * $\alg{process} (\ pi) \to d_\pi \,$ : Verarbeiten Sie die gegebene Permutation $\pi \in S_n$ und zeigen Sie ihre kompakte Darstellung $d_\pi$, * $\alg{eval}(d_\pi,x)\ zu y an \,$ : bei Eingabe $ d_\pi$ und $x \in \range{n}$, Ausgabe $y = \pi(x)$. Wir benötigen, dass $\alg{eval}(\cdot,\cdot)$ schnell ist, was bedeutet, dass seine Ausführung höchstens $O(\log n)$ betragen darf. Der Algorithmus $\alg{process}(\cdot)$ kann in $n$ in polynomieller Zeit ausgeführt werden. Unser Ziel ist es, eine Datenstruktur zum Speichern einer Permutation zu entwerfen, bei der die ungünstigste Größe von $d_\pi$, gemessen in Bits, so klein wie möglich ist. Mit „Worst Case“ meinen wir den schlechtesten Fall über alle $\pi \in S_n$. Für zusätzliche Bonuspunkte möchten wir auch, dass die Datenstruktur eine schnelle Inversion unterstützt: * $\alg{invert}(d_\pi, y) \to x\,$: on input $d_\pi$ and $y \in \ Bereich {n}$, Ausgabe $x = \pi^{-1}(y)$. Dieser Algorithmus sollte ebenfalls höchstens $O(\log n)$ in der Zeit laufen. ## Die triviale Lösung Angenommen, $n$ ist eine Potenz von 2. Die triviale Datenstruktur zum Speichern einer Permutation $\pi \in S_n$ listet einfach die Elemente der Permutation der Reihe nach auf. Das heißt, * $\alg{process}(\pi)$ erzeugt $d_\pi \deq \bigl[\pi(0),\ \pi(1),\ \ldots,\ \pi(n-1) \bigr]$ und * $\alg{eval}(d_\pi, x)$ generiert $d_\pi[x]$ für $x \in \range{n}$. Zum Beispiel haben wir für die Permutation $\pi_1$ in $\eqref{eq:exmpl}$ oben $$ d_{\pi_1} \deq[1010\; 1100\; 1101\; 1001\; 0111\; 0010\; 1110\; 0011\; 1011\; 1111\; 0000\; 0110\; 0100\; 0001\; 0101\; 1000].$$ Diese triviale Datenstruktur hat die folgenden Eigenschaften: * die Länge von $d_\pi$ beträgt immer $n \log_2 n$ Bits, und * $\alg{eval}(\cdot,\cdot)$ läuft in konstanter Zeit. Es sieht ziemlich gut aus. Also, sind wir fertig? Also...