Revealing and Utilizing the Hidden Structure for Solving Hard Problems in AI

An vielen Schlusselstellen der Informations- und Kommunikationstechnik ¨ werden neue und immer m¨achtigere Algorithmen ben¨otigt, um den weiteren technologischen Fortschritt zu gew¨ahrleisten. Ein vierj¨ahriges Forschungsprojekt an der TU Wien hat sich genau damit besch¨aftigt, mit beeindruckenden Ergebnissen. Das Projektteam hat gezeigt, dass viele als praktisch unl¨osbar geltende Probleme der kunstlichen Intelligenz eine versteckte Struktur aufweisen. ¨ Findet man diese und nutzt sie geschickt aus, werden die Probleme pl¨otzlich l¨osbar. Ein konkretes Beispiel: Bei der Verarbeitung logischer Programme w¨achst die Rechenzeit exponentiell mit der Anzahl der Variablen, was das L¨osen gr¨osserer Eingaben verunm¨oglicht. Die Forscher haben eine Methode entwickelt, bei der die Explosion der Rechenzeit einged¨ammt werden kann. Die Ergebnisse sprechen fur sich: ¨ uber hundert wissenschaftliche Publikationen ¨ und mehrere preisgekr¨onte Softwaresysteme. Das DPDB-System etwa nutzt Datenbanktechnologie fur komplexe Berechnungen, ein anderes System brach ¨ Rekorde im Generieren von kleinsten Schaltkreisen die eine gegebene Boolsche Funtion berechnen. Besonders spannend sind die neuen mathematischen Konzepte, die das Team entwickelt hat. Eine Methode zerlegt komplexe Formeln geschickt in kleinere Teile, die jeweils einfach zu l¨osen sind, wie ein großes Puzzle, das man in handhabbare Stucke aufteilt. Oder die Arbeit zur Twin-Width, wo erstmals ¨ praktikable Berechnungsmethoden um diese Invariante exakt zu bestimmen. Ein sch¨oner Nebeneffekt: Effizientere Algorithmen bedeuten weniger Stromverbrauch. Wenn ein Problem statt in Tagen in Minuten gel¨ost wird, freut sich auch das Klima. Die Software des Projektes ist frei verfugbar: gelebte Open Science. ¨ Die Zukunft der KI wird damit ein Stuck handhabbarer.