Die Dozenten der Informatik-Institute der Technischen Universität Braunschweig laden im Rahmen des Informatik-Kolloquiums zu folgendem Vortrag ein.

Dr. Markus Kroetzsch, Technische Universität Dresden: P ≠ P: Warum einige P-vollständige Probleme härter sind als andere

Beginn: 18.02.2015, 14:00 Uhr Ort: TU Braunschweig, Informatikzentrum, Mühlenpfordtstraße 23, 1. OG, Hörsaal M 161 Webseite: http://www.ibr.cs.tu-bs.de/cal/kolloq/2015-02-18-kroetzsch.html Kontakt: Prof. Dr.-Ing. Ina Schaefer

Die mit polynomiellem Zeitaufwand lösbaren Probleme der Klasse P(Time) gelten oft als gut handhabbar und nahezu beliebig skalierbar. In der Praxis sieht das meist anders aus. Während einige P-vollständige Probleme in linearer Zeit gelöst werden können, sind für andere nur Algorithmen mit sehr viel schlechterem Skalierungsverhalten bekannt. Dabei ist schon ein kubisches Zeitverhalten in vielen Anwendungen nicht praktikabel. Leider kann die klassische Komplexitätstheorie nicht erklären, warum manche P-vollständige Probleme härter zu sein scheinen als andere.

In diesem Vortrag untersuchen wir diese Frage konkret für Probleme des logischen Schließens. Deren Besonderheit ist es, dass Berechnungen meist durch ein System von Inferenzregeln (Kalkül) beschrieben werden. Überraschenderweise lässt sich zeigen, dass die Lösung verschiedener P-vollständiger Probleme zum Teil unterschiedlich ausdrucksstarke Kalküle verlangt. Dadurch erhalten wir einen alternativen Begriff der "Härte" eines Problems, bei dem wir die Ausdrucksstärke von Kalkülen vergleichen, ähnlich zu (aber nicht identisch mit) Ansätzen aus der deskriptiven Komplexität. Wir diskutieren die praktische Bedeutung dieser Einsichten anhand von konkreten Problemen aus Wissensrepräsentation und Semantic Web, mit teils überraschenden Ergebnissen.