Konferenzbeitrag
Parametrisierte Komplexität in der polynomiellen Hierarchie
Lade...
Volltext URI
Dokumententyp
Text/Conference Paper
Zusatzinformation
Datum
2017
Autor:innen
Zeitschriftentitel
ISSN der Zeitschrift
Bandtitel
Verlag
Gesellschaft für Informatik e.V.
Zusammenfassung
In dieser Arbeit erweitern wir die Theorie der parametrisierten Komplexität, um Probleme, die von häheren Ebenen der polynomiellen Hierarchie stammen, adäquat analysieren zu kännen. Wir erweitern die bekannten Konzepte und Methoden in grundlegender Weise, um auch die bemerkenswerte Effektivität von existierenden SAT-Solvern theoretisch zu berücksichtigen. Wir demonstrieren, dass unser neues Instrumentarium es ermöglicht, die exakte Komplexität einer Vielzahl von fundamentaler Berechnungsproblemen zu bestimmen, und in Folge deren theoretische Schwere einzuordnen und zu vergleichen. Die betrachteten Probleme stammen aus vielen Bereichen der Informatik, z.B. der Künstlichen Intelligenz, Wissensräpresentation, Verifikation und Optimierung.