P und beschreibende Komplexität

Im Complexity Zoo heißt es [ 1 ], dass $P$ in der beschreibenden Komplexität durch drei verschiedene Arten von Formeln definiert werden kann: $FO(LFP)$ das auch $FO(n^{O(1)})$ , und auch als $SO(HORN)$ .

Es gibt jedoch einige Ausnahmen sind zum Beispiel $Evenness$ kann nicht durch FP ausgedrückt werden (FP hat die gleiche Ausdruckskraft mit LFP). $Connectivity$ und $2-colourability$ durch Logik erster Ordnung nicht definierbar sind. Einige Probleme können nicht einmal mit einer endlichen Anzahl von Variablen wie axiomatisiert werden $Evenness$ , $Perfect~Matching$ , $Hamiltonicity$ .

Immerman schlug vor, dass Fixpunktlogik + Zählung (FPC) eine mögliche Logik für die Erfassung von P sein könnte.

Cai Furer, Immerman zeigte jedoch, dass es Polynom-Zeit-Graph-Eigenschaften gibt, die in FPC nicht exprimierbar sind [ 2 ]. Das Problem der Lösung linearer Gleichungen über das Zwei-Elemente-Feld ist in der Infinitärlogik mit Zählung nicht definierbar [ 3 ]. Weitere Informationen finden Sie in [ 4 ].

Welche logische Struktur kann P im Allgemeinen erfassen? Die positive Antwort ist, dass eine Klasse geordneter endlicher Strukturen in der Logik der kleinsten Festpunkte genau dann definierbar ist, wenn sie in P von Immerman [ 5 ] und Vardi [ 6 ] entscheidbar ist. Wie wäre es mit dem ungeordneten Fall? Können Sie weitere Gegenbeispiele der Aussage im Komplexitätszoo zeigen?

lo.logic polynomial-time descriptive-complexity Rupei Xu
quelle

Hier ist ein Tutorial, das einen Überblick über die Ergebnisse dieser speziellen Frage gibt: cl.cam.ac.uk/~ad260/talks/wollic-tutorial.pdf

Denis

@ Denis Danke, Denis! Dieses Tutorial enthält mehr logische Strukturen für P. Wenn wir traditionell über ein Problem sprechen, das durch Polynome zeitlich lösbar ist, denken wir, dass es "einfach" ist. Die logischen Strukturen von P sehen jedoch so kompliziert aus, und es gibt immer noch viele unbekannte Fälle und offene Probleme.

Rupei Xu

Ja, es scheint, dass die Menge der "einfachen" Probleme (dh P) nicht so gut strukturiert ist und schwer mit so etwas wie "die einfachen Probleme sind diejenigen, die aus den Grundproblemen A, B, erhalten werden können, zu charakterisieren sind. C, kombiniert auf X, Y ". Es gibt immer einfachere Probleme anderer Art, die clevere Polynomalgorithmen mit neuen Ideen erfordern.

Denis

Antworten:

Martin Grohe hat in dieser Frage in letzter Zeit erhebliche Fortschritte erzielt. Er gibt eine Logik zur Erfassung der Polynomzeit für Klassen von Graphen an, die in eine feste Oberfläche eingebettet werden können: https://dl.acm.org/citation.cfm?doid=2371656.2371662 Bearbeiten: Der allgemeine Fall scheint ungelöst zu sein (aber ich bin keineswegs ein Experte auf diesem Gebiet).

Hermann Gruber
quelle

Ja. Es gibt viele algorithmische Meta-Theorem-Ergebnisse (wie das berühmte Courcelle-Theorem), die die einfachen Fälle erfassen können. Der folgende Link ist ein gutes Umfragepapier. people.cs.umass.edu/~immerman/pub/… Diese Ergebnisse haben jedoch auch die Einschränkung für die Diagrammstrukturen, auf denen das Problem ausgeführt wird, wie z. B. Baum, begrenzte Baumbreite, planare Diagramme, kleinere geschlossene Diagramme usw. Es gibt Bisher kann keine vollständige Logikstruktur P in allgemeinen Graphen ohne Reihenfolge erfassen.

Rupei Xu

Ich denke, dass Grohes Arbeit etwas ganz Besonderes ist, weil in diesem Fall die Logik P in einer bemerkenswert großen Klasse von Graphen erschöpft, dh es gibt keine Gegenbeispiele. Wenn ich es richtig verstanden habe, ist es schwierig, erschöpfend zu sein. Die von Ihnen erwähnten MSO-Ergebnisse scheinen diese Funktion nicht zu haben. Aber ich mein Fachwissen in dieser Hinsicht ist sehr begrenzt, ich kann mich hier irren.

Hermann Gruber