In der Komplexitätstheorie geht es um die Frage, wie aufwändig die Lösung bestimmter Probleme ist. Gibt es eine Methode, in kurzer Zeit zum korrekten Ergebnis zu kommen, oder handelt es sich um eine Aufgabe, die aus ganz prinzipiellen Gründen extrem aufwändig ist? Damit beschäftigt sich Markus Hecher aus der Forschungsgruppe von Prof. Stefan Woltran (Databases and Artificial Intelligence) am Institut für Logic and Computation der TU Wien.

„Man kann logische Aussagen untersuchen, um festzustellen, ob sie wahr oder falsch sind. Man kann aber auch logische Programme untersuchen – das kann zum Beispiel eine Liste von Regeln sein, die eine künstliche Intelligenz befolgen soll, um ein bestimmtes Ziel zu erreichen“, erklärt Markus Hecher. „Dann kann man die Frage stellen: Ist das Ziel mit diesen Regeln prinzipiell erreichbar oder nicht? Und wenn ja: Wie aufwändig ist es, eine Lösung zu finden?“

Regeln, die miteinander verknüpft sind

Dabei kann es sich zum Beispiel um die Aufgabe handeln, den kürzesten Weg zwischen zwei Adressen zu finden. Oder um das Erstellen komplizierter Pläne: Wenn man etwa einen Stundenplan für eine Schule erstellen möchte, muss man eine lange Liste von Regeln beachten: Jede Klasse kann zu jedem Zeitpunkt nur ein Unterrichtsfach zugeteilt bekommen, jeder Raum darf nur einfach belegt sein, und die Lehrpersonen können immer nur eine Klasse unterrichten. Und alle Anforderungen müssen jeweils mit den anderen zusammenpassen.

„Man kann solche Aufgaben in Form von Graphen aufzeichnen“, sagt Markus Hecher. „Daran kann man dann sehen, wie die Regeln logisch miteinander verknüpft sind.“ Sind sie aufgebaut wie ein Baum, bei dem die Äste sich in immer kleinere Zweige aufteilen, dann ist das Problem relativ einfach zu lösen. Schwierig wird es, wenn wir es mit komplexeren logischen Verknüpfungen zu tun haben, wenn die logischen Vorschriften Kreise bilden und alle Bereiche des Graphen mit allen anderen in einer logischen Verbindung stehen. „Man kann sogar eine Zahl angeben, mit der man misst, wie baumähnlich eine solche Struktur ist“, erklärt Markus Hecher. „Das ist die sogenannte Baumweite.“

Prestigeträchtige Auszeichnung

Hecher untersucht, wie die Baumweite mit dem Aufwand zusammenhängt, der zur Lösung einer Aufgabe nötig ist. Er konnte zeigen, dass die Auswertung bestimmter logischer Programme aufwändiger ist, als man bisher dachte – aufwändiger als die Auswertung gewöhnlicher Logik-Aussagen desselben Komplexitätsgrades (unter üblichen Annahmen der Komplexitätstheorie). Dafür wurde er nun bei der renommierten „KR“-Konferenz (International Conference on Principles of Knowledge Representation and Reasoning), öffnet eine externe URL in einem neuen Fenster mit dem „Marco Cadoli Best Student Paper Award" ausgezeichnet. Die TU Wien war bei der Konferenz überhaupt sehr stark vertreten – mit insgesamt 13 Beiträgen, darunter eine Keynote-Lecture von Prof. Thomas Eiter.

„Unsere Forschung dient dazu, besser zu verstehen, welche Arten von Aufgaben schwieriger zu lösen sind als andere – und gleichzeitig helfen unsere Ergebnisse auch dabei, bessere Lösungs-Algorithmen für künstliche Intelligenzen zu entwickeln“, sagt Markus Hecher.