Parameterisierte Komplexität eröffnet Lösbarkeit von Pearl's Kausalhierarchie

Die Pearl's Causal Hierarchy (PCH) bildet das Rückgrat moderner kausaler Analyse, doch die Frage, ob eine gegebene PCH-Formel erfüllbar ist, gilt in nahezu allen klassischen Szenarien als rechnerisch unlösbar. In einer neuen Veröffentlichung wird dieses Problem aus der Perspektive der parametrisierten Komplexität neu beleuchtet und die ersten Wege zur Trägerschaft von Lösbarkeit aufgezeigt.

Die Autoren präsentieren feste Parameter- und XP‑Algorithmen für die Erfüllbarkeitsprüfung in wichtigen probabilistischen und kontrafaktischen Teilbereichen. Dabei werden Parameter wie die primale Baumweite und die Anzahl der Variablen herangezogen, während gleichzeitig zugehörige Schwere‑Beweise die Grenzen der Trägerschaft klar definieren.

Ein entscheidender technischer Fortschritt besteht darin, das herkömmliche dynamische Programmierparadigma, das häufig bei baumweitenbasierten Verfahren zum Einsatz kommt, zu verlassen. Stattdessen nutzt die Arbeit strukturelle Charakterisierungen gut geformter kausaler Modelle, was ein völlig neues algorithmisches Werkzeug für kausale Überlegungen bereitstellt.

Diese Ergebnisse markieren einen bedeutenden Schritt vorwärts: Sie eröffnen nicht nur theoretische Einblicke in die Komplexitätsstruktur von PCH, sondern liefern auch praktische Algorithmen, die effiziente kausale Analyse in bislang unzugänglichen Bereichen ermöglichen.