Eine Eskalation der benötigten Rechenressourcen (Zeit, Speicher, Zwischenspeicher), verursacht durch syntaktische Merkmale, Kodierungen, algorithmische Entscheidungen oder spezifische Probleminstanzen, die die Berechnung unpraktikabel machen.

Prinzip

Bestimmte Kodierungen oder Transformationen können die Repräsentationsgröße oder Zwischenstrukturen vergrößern (z. B. Duplizieren von Teil-Ausdrücken oder Expansion von Quantoren), und algorithmische Prozesse können im Worst‑Case einen Ressourcenbedarf haben, der superpolynomiell mit der Eingabegröße wächst.

Demonstration

Die Umwandlung einer Formel in disjunktive Normalform (DNF) kann exponentiell in der Länge aufblähen; das sofortige Auflösen von Definitionen oder naives Grounding quantifizierter Formeln in einer großen Domäne kann Speicher und Zeit erschöpfen, obwohl die ursprüngliche Spezifikation kompakt ist.

Fehlanwendung

Kodierungen oder Algorithmen wählen, die implizit exponentiell viele Zwischenresultate materialisieren (z. B. komplette Expansion kombinatorischer Konstrukte), in der Annahme, dass die Problemgröße klein bleibt, was zu Abstürzen oder unbeherrschbaren Laufzeiten führt.

Konsequenz

Das Bewusstsein für Ressourcenexplosion führt zu alternativen Kodierungen, fauler Auswertung, symbolischen Repräsentationen, Streaming oder Approximationsalgorithmen; korrekt adressiert stellt dies die Praktikabilität und vorhersehbare Ressourcenbegrenzung für beabsichtigte Anwendungsfälle wieder her.

Umkehrung

Ressourcenkontrolle — algorithmische und repräsentationelle Entscheidungen, die Zeit und Speicher innerhalb akzeptabler Grenzen halten (z. B. polynomialzeitliche Kodierungen, Streaming-Algorithmen, inkrementelle Methoden).

Abgrenzung

Bezieht sich auf Ressourcenkosten, die aus Repräsentationen, Kodierungen oder algorithmischen Expansionen entstehen; unterscheidet sich von bloßer algorithmischer Komplexitätsklassifikation (z. B. P vs NP), insofern die Explosion oft aus bestimmten Kodierungen oder Preprocessing-Schritten statt aus inhärenter Entscheidungs­komplexität resultiert.

Semantische Spannung

Eng verwandt mit Suchraum-Explosion: das eine beschreibt das kombinatorische Wachstum von Kandidaten, das andere betont die tatsächlich gemessenen Ressourcen; Gegenmaßnahmen überschneiden sich, können aber mehr Gewicht auf Speicherlayout, Streaming und inkrementelle Auswertung legen statt auf Suchheuristiken.

Synthese

Ressourcenexplosion ist der praktische Fehlermodus, bei dem Repräsentationen oder algorithmische Schritte unpraktisch große Zeit‑ oder Speicheranforderungen erzeugen; ihre Lösung erfordert Kodierungen und Evaluationsstrategien, die die Materialisierung großer Zwischenstrukturen vermeiden und Faulheit, Modularität oder Approximation nutzen.