KI News: Kurz und klar.

In der Welt der Graphentheorie sind strukturelle Messgrößen wie der Treewidth zentrale Werkzeuge, die effiziente Algorithmen ermöglichen, wenn man sie als Parameter nutzt. Besonders bekannt ist, dass moderne SAT‑Solver bei Instanzen mit kleinem Treewidth sehr schnell arbeiten. Da diese Solver weit verbreitet sind, besteht ein starkes Interesse an kompakten Encodings in (Q)SAT, um sowohl Lösungen zu finden als auch die Grenzen solcher Encodings zu verstehen.

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.