Parametrisierte Komplexität in der polynomiellen Hierarchie

Abstract

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.