Drei Verständnisebenen
01 · Das Problem verstehen
Die Determinante kombiniert Einträge einer quadratischen Matrix. Die Permanente summiert ähnliche Produkte ohne wechselnde Vorzeichen. Diese kleine Änderung führt zu einer anderen Rechenaufgabe.
02 · Den Beitrag verstehen
Gemeldet werden neue untere Schranken für arithmetische Schaltkreise und Formeln, darunter eine Formelschranke der Größenordnung n⁴/log n für die Permanente.
03 · Akademische Einordnung
Eine arithmetische Formel darf Zwischenergebnisse nicht so frei wiederverwenden wie ein allgemeiner Schaltkreis. Eine Formelschranke ist daher keine identische Schranke für alle Algorithmen. Körper, Konstanten, Uniformität und genaue Modellklasse gehören zur Aussage.
Mögliche Auswirkungen
Möglicher Fortschritt bei Methoden zum Nachweis unvermeidbarer algebraischer Rechenkosten.
Was NICHT bewiesen ist
Dies löst P gegen NP nicht. Eine Schranke in einem eingeschränkten Rechenmodell ist keine allgemeine Software-Laufzeitschranke.