WENN EINE 1 MEHR KOSTET ALS EINE 0, WIRD KOMPRESSION SCHWER

Um einen Text kompakt zu speichern oder zu senden, gibt man jedem Symbol ein Wort aus Nullen und Einsen, kurz für häufige Symbole und länger für seltene. Die Wörter müssen einen Präfixcode bilden: Kein Wort darf der Anfang eines anderen sein. {0, 10, 11} funktioniert; {0, 01, 11} nicht, weil 01 mit 0 beginnt. Mit einem Präfixcode lässt sich eine lange Bitfolge ohne jedes Trennzeichen wieder in Wörter zerlegen.

Den besten solchen Code – den mit der kleinsten mittleren Länge – fand 1952 D. A. Huffman, mit einem einfachen gierigen Verfahren (greedy), das schnell läuft.

Wenn Buchstaben einen Preis haben

Huffmans Rezept setzt voraus, dass eine 0 und eine 1 gleich viel kosten. Angenommen, das ist nicht so: Die 1 braucht länger zur Übertragung oder mehr Platz zum Speichern. Dann kostet jedes Wort die Summe seiner Buchstaben, und die Zusammensetzung eines Wortes zählt ebenso viel wie seine Länge. Bei Kosten von 1 und 3 zum Beispiel sind 00 und 01 gleich lang, kosten aber 2 und 4.

Diese Variante hat eine lange Geschichte. R. M. Karp formulierte sie 1961 als Problem der ganzzahligen Optimierung. Spätere Arbeiten fanden exakte, effiziente Algorithmen für jedes feste Paar ganzzahliger Kosten sowie ein Approximationsschema, das dem Optimum beliebig nahe kommt. Doch wenn die Kosten selbst Teil der Eingabe sind, wusste niemand, wie schwer das Problem ist. Noch 2021 wurde es als offen geführt.

Die Antwort: NP-vollständig

L. Sunil Chandran vom Indian Institute of Science in Bengaluru und Rishikesh Gajjala von Pramaana Labs beweisen nun, dass die Entscheidung, ob ein Code mit Kosten von höchstens K existiert, NP-vollständig ist – selbst wenn die beiden Kosten aufeinanderfolgende ganze Zahlen sind, M und M + 1. In der Informatik heißt ein Problem NP-vollständig, wenn es so schwer ist wie eine ganze Familie klassischer Probleme: Eine schnelle allgemeine Methode für eines davon würde eine für alle liefern, und keine ist bekannt. Den billigsten Code zu finden, ist daher NP-schwer.

Das steht nicht im Widerspruch zu den schnellen Algorithmen für feste Kosten. Im Beweis wächst M mit der Eingabe; für jedes im Voraus festgelegte Kostenpaar gelten diese Algorithmen weiterhin.

Ein Rätsel, versteckt in einem Codebaum

Der Beweis geht von einem bekannten schweren Problem aus: Kann man in einem Netzwerk, das ohne Kreuzungen auf ein Blatt Papier gezeichnet ist, k Punkte auswählen, von denen keine zwei miteinander verbunden sind? Dann konstruiert er ein Codierungsproblem, dessen billigster Code diese Frage beantwortet.

1. Jeder Präfixcode ist ein Baum: 0 geht nach links, 1 nach rechts. Ein Wort der Tiefe d mit z Einsen kostet M × d + z, wenn die Buchstaben M und M + 1 kosten. Die Tiefe bestimmt den großen Teil der Kosten, die Zahl der Einsen den kleinen.
2. Das Team entwirft ein neues Zwischenproblem: Man legt fest, wie viele Blätter der Baum auf jeder Tiefe hat, und bewertet, wo seine Blätter sitzen. Es zeigt, dass ein billiger Baum, während er Ebene für Ebene wächst, ein kleines Programm ausführen muss, das die gewählten Punkte einen nach dem anderen prüft, jede Wahl kopiert und jede Verbindung testet. Jede Abkürzung kostet mindestens eine Einheit mehr; jeder gewählte Punkt spart genau eine.
3. Schließlich werden die Häufigkeiten so abgestimmt, dass jedes Symbol auf die richtige Tiefe gezwungen wird, und die Bewertung wird zu den Codierungskosten plus einem festen Betrag.

Ein kleines Beispiel aus dem Paper zeigt, wie subtil die Kosten sind. Drei Symbole haben die Häufigkeiten 20, 12 und 9, und die Buchstaben kosten 83 und 84. Der Code (0, 10, 11) kostet 5.176. Der Code (1, 00, 01) kostet 5.175: Den teuren Buchstaben dem häufigsten Symbol zu geben, gewinnt, weil die beiden anderen Wörter dann weniger Einsen tragen.

Wo die Schwierigkeit steckt

Ein zweites Ergebnis verortet das Problem mitten in der gewöhnlichen Codierung. Huffmans Rezept findet die kürzeste mittlere Länge schnell. Doch unter allen Codes, die diese Länge erreichen, denjenigen mit den wenigsten Einsen, gewichtet nach Häufigkeit, auszuwählen, ist ebenfalls NP-vollständig.

Es bleiben Fragen offen: ob das Problem schwer bleibt, wenn alle Zahlen klein sind (sogenannte starke NP-Schwere), und ob ein schnelles Schema das Optimum mit beliebiger Genauigkeit annähern kann, mit einer Laufzeit, die auch mit dieser Genauigkeit vernünftig wächst.

Ein mit einer KI gefundener Beweis

Das Paper legt offen, wie es entstanden ist. Das Team bat OpenAIs Codex zunächst um einen Beweis der Schwere eines allgemeineren Problems und dann darum, ihn auf nichtbinäre und schließlich auf binäre Codes auszuweiten. Codex trug zur Strategie der Reduktion und zu ihrer mathematischen Ausarbeitung bei; es half auch beim Formulieren, beim Prüfen von Argumenten und beim Konstruieren von Beispielen. Das Team lenkte die Arbeit, verlangte Korrekturen und Vereinfachungen, schrieb die Darstellung in weiten Teilen neu und übernimmt die Verantwortung für die endgültigen Aussagen und Beweise. Wie jeder Preprint hat die Arbeit noch kein Peer-Review durchlaufen.