Wie wenige Bausteine reichen aus, um eine Rechenaufgabe zu lösen? Für eine gezielt konstruierte Aufgabe setzen zwei Informatiker die bewiesene Mindestzahl jetzt höher an. Om Swostik Mishra und Rahul Santhanam von der Universität Oxford zeigen in einem neuen Autorenpreprint: Eine bestimmte boolesche Funktion braucht bei vielen Eingangsbits annähernd 3,5 Logikgatter pro Bit. Die bisher beste entsprechende Untergrenze lag bei 3,1. Interessant ist vor allem der neue Blick auf die Schaltung, mit dem die Autoren die Grenze verschieben.
Das Manuskript ist beim Electronic Colloquium on Computational Complexity mit dem Datum 19. Oktober 2026 verzeichnet. Es behandelt eine Grundfrage der Informatik: Wie lässt sich beweisen, dass auch die geschickteste Verdrahtung unter einer bestimmten Größe scheitern muss?
Zwei Eingänge, eine Entscheidung
Ein Logikgatter verarbeitet Nullen und Einsen. Ein UND-Gatter liefert beispielsweise nur dann eine Eins, wenn beide Eingänge Eins sind. Ein XOR-Gatter liefert eine Eins, wenn sich seine beiden Eingänge unterscheiden. Aus solchen kleinen Entscheidungen lassen sich große Berechnungen zusammensetzen.
Im untersuchten Modell darf jedes Gatter eine beliebige boolesche Funktion von höchstens zwei Eingängen ausführen. Sein Ergebnis darf an beliebig viele weitere Gatter gehen. Gezählt werden die Gatter im Netzwerk. Diese sogenannte B2-Basis gibt dem Schaltungsentwurf viel Freiheit. Wer dafür eine Untergrenze beweist, muss also auch ungewöhnliche, besonders sparsame Konstruktionen ausschließen.
Eine funktionierende Schaltung zu bauen, zeigt, wie viele Gatter ausreichen. Eine Untergrenze verlangt den umgekehrten Nachweis: Jede kleinere Schaltung muss für mindestens eine Eingabe ein falsches Ergebnis liefern. Dafür genügt es nicht, einige erfolglose Entwürfe durchzuprobieren.
Was sich von 3,1 auf 3,5 verschiebt
Die Autoren geben die neue Grenze im Hauptsatz genauer als 3,5n minus einen Korrekturterm an, der höchstens logarithmisch mit n wächst. Dabei ist n die Zahl der Eingangsbits. Bei sehr großen Eingaben gewinnt deshalb der Faktor 3,5 an Gewicht. Im Titel des Manuskripts steht die allgemeinere Schreibweise 3,5n − o(n): Der abgezogene Anteil wird im Verhältnis zu n immer kleiner.
Die frühere Bestmarke von 3,1n − o(n) schreiben Mishra und Santhanam einer Arbeit von Jiatu Li und Tianqi Yang aus dem Jahr 2022 zu. Beide Grenzen betreffen explizit beschreibbare Funktionen. Die neue Aufgabe lässt sich außerdem in Polynomialzeit berechnen, gehört also zur Komplexitätsklasse P. Sie ist keine bloß durch ein Existenzargument garantierte, ansonsten unbekannte Rechenvorschrift.
Der Trick steckt im Umordnen
Der Beweis setzt bei der Gatterelimination an. Dabei werden Eingaben eingeschränkt und dadurch Teile einer Schaltung überflüssig. Setzt man etwa einen Eingang eines UND-Gatters auf Null, steht sein Ausgang fest. Nachfolgende Gatter können sich ebenfalls vereinfachen. Beim XOR reicht ein auf Null gesetzter Eingang dagegen den Wert des anderen Eingangs durch.
Bleibt die betrachtete Funktion trotz vieler solcher Schritte anspruchsvoll genug, lässt sich aus den entfernten Gattern auf die notwendige Ausgangsgröße schließen. Die Autoren nutzen dafür sogenannte affine Disperser: Funktionen, die auf ausreichend großen affinen Teilräumen der Eingaben weiterhin unterschiedliche Ergebnisse liefern.
Neu ist, dass Mishra und Santhanam nicht nur die ursprünglichen Eingangsvariablen bearbeiten. Sie beschreiben deren Werte mithilfe unabhängiger Parameter und passen diese Beschreibung während des Beweises an. So können sie bestimmte Engpässe durch Umparametrisieren behandeln. Die Freiheitsgrade werden anders geordnet, bevor weitere Einschränkungen folgen. Laut Manuskript verbessert das die Grenze und vereinfacht zugleich die Beweisführung gegenüber den Vorarbeiten.
Der Fortschritt liegt damit im Verständnis dessen, was Berechnungen mindestens benötigen. Das Maß zählt abstrakte Gatter für die untersuchte Funktion; reale Chipfläche, Transistorzahl und Stromverbrauch hängen zusätzlich von Bauteilen und Umsetzung ab. Für die Komplexitätstheorie ist die höhere Schranke dennoch wertvoll: Sie zeigt genauer, wo selbst ein sehr freies Schaltungsmodell an seine Spargrenze stößt.
Quellen
- Om Swostik Mishra und Rahul Santhanam, Universität Oxford: An Explicit 3.5n-o(n) Size Lower Bound against General Boolean Circuits, ECCC TR26-260, Autorenpreprint, 19. Oktober 2026; Originalmanuskript (PDF), abgerufen am 19. Oktober 2026.
Für diesen Artikel wurden KI-gestützte Recherche- und Editierwerkzeuge verwendet. Der Inhalt wurde redaktionell geprüft.
