- Teilnehmer:
- Arne Meier (Projektleiter deutsche Seite)
- Raghavendra Rao B. V. (Projektleiter indische Seite)
- Anselm Haak
- Om Prakash
- Dauer: 2018-2019
- Gefördert durch: DAAD PPP Indien DST
- Ergebnisse des Projekts wurden auf der STACS 2021 veröffentlicht (Link)
Projektbeschreibung
Die Theorie der parametrisierten Komplexität (Downey, Fellows 1999) betrachtet sogenannte Parametrisierungen, um die inhärente Schwierigkeit von Problemen besser zu verstehen. Ein einfaches Beispiel für eine solche Parametrisierung ist für das Erfüllbarkeitsproblems aussagenlogischer Formeln (SAT) die Anzahl der Variablen einer gegebenen Formel. Unter dieser Parametrisierung kann man SAT in einer Laufzeit von 2•|Vars(F)|•|F| lösen, wenn F die gegebene Formel ist. Solche Laufzeiten bezeichnet man als "fixed-parameter tractable" (oder kurz, in FPT). Das bedeutet, wenn der Parameter als konstant gesehen wird, ist die Laufzeit polynomiell und der Grad des Polynoms hängt nicht vom Wert des Parameters ab. Im Gegensatz hierzu stehen Laufzeiten der Form n•f(k) deren zugehörige Probleme in der Klasse XP zusammengefasst werden (für Eingabelänge n). Zwischen FPT und XP existiert eine Hierarchie sogenannter "Weft"-Klassen W[i]. Es ist nicht bekannt, ob jegliche der Inklusionen von W[i] zu W[i+1] strikt ist oder ob FPT strikt in W[1] enthalten ist.
Zählprobleme spielen eine Schlüsselrolle bei vielen Durchbrüchen in der strukturellen Komplexitätstheorie. Vor einer Dekade haben Flum und Grohe (2002) eine Theorie von parametrisierten Zählproblemen entwickelt. Flum und Grohe zeigten, dass das Zählen von Zyklen der Länge k in einem gerichteten Graph vollständig für die Klasse #W[1] ist (welches die Zählversion der Klasse W[1] ist; üblicherweise werden hier die Anzahl von akzeptierenden Pfaden gezählt). Weiterhin wurde das Zählen von Lösungen von Model-Checking-Problemen über erststufiger Logik verwendet, um die sogenannte #A-Hierarchie zu charakterisieren. Trotz intensivem Forschungsaufwand blieb bisher ein Erfolg aus, klassische Resultate, wie zum Beispiel den Satz von Toda in die parametrisierte Welt zu übersetzen.
In der deskriptiven Komplexitätstheorie werden Komplexitätsklassen durch Mengen von Formeln charakterisiert. In einem bahnbrechenden Resultat zeigte Fagin (1973), dass die Klasse NP mit der Menge aller existentiellen zweitstufigen Formeln zusammenfällt. Von Immerman (1982) ist eine Charakterisierung der Klasse P bekannt sowie, dass reguläre Sprachen durch monadische zweitstufige Formeln (MSO) charakterisiert werden können. Saluja und Subrahmaniam (1998) erreichten eine logische Charakterisierung von #P durch das Zählen von Modellen einer FO Formel. Darüber hinaus klassifizierte Kontinen (2008) die Zählhierarchie durch Logiken mit verallgemeinerten Quantoren. Flum und Grohe zeigten 2003, dass logische Charakterisierungen von klassischen Komplexitätsklassen, wie P, NP und PSPACE auch auf den parametrisierten Ansatz übertragen werden können. Des Weiteren gaben sie 2007 eine logische Charakterisierung der W*-Hierarchie an.
In diesem Projekt wollen wir parametrisierte Entscheidungs- und Zählklassen durch Mengen logischer Formeln charakterisieren. Wir unterteilen das Projekt in zwei Abschnitte.
- Charakterisierung von parametrisierten Komplexitätsklassen
Wie bereits erwähnt besitzt die W*-Hierarchie eine Fagin-artige Charakterisierung durch logische Formeln. Jedoch gibt es bisher keinen solchen Ansatz für die W-Hierarchie, für FPT oder andere bzgl. Parallelität und Platz beschränkte Klassen. Wir planen logische Charakterisierungen von FPT und parametrisierten Varianten von Komplexitätsklassen, wie para-AC[0], para-WNC[1], para-WL und para-WNL welche von Elberfeld, Stockhusen und Tantau (2015) definiert wurden, zu finden. - Charakterisierung von parametrisierten Zählklassen
Bisher sind keine logischen Charakterisierungen von den von Flum und Grohe eingeführten parametrisierten Zählklassen bekannt. Wir beabsichtigen Klassen innerhalb der #W[P] Hierarchie zu beschreiben. Genauer, wir werden an folgenden Fragestellungen arbeiten:- Finde Charakterisierungen von #W[1] und #W[P] bzgl. Zählen über FO oder andere zugehörige Logiken.
- Finde logische Charakterisierungen der parametrisierten Analogen der Polynomialzeithierarchie von Montoya (2008).
- Versuche die logische Charakterisierung der Zählhierarchie von Kontinen (2009) auf die parametrisierte Fragestellung zu übertragen.
Innerhalb beider Abschnitte werden wir Parametrisierungen natürlicher Zählprobleme, wie das Zählen von Pfaden in gerichteten Graphen oder Pfade in Kellerautomaten, genauer untersuchen. Außerdem stellt sich die Frage wie Werkzeuge der endlichen Modelltheorie (Lokalität, Ehrenfeucht-Fraïssé Spiele, Zero-One Laws, ...) genutzt werden können, um Antworten zu den obigen Fragen zu finden.
