Korrespondenz zwischen Komplexitätsklassen und Logik

33

Ich habe einmal einen Kurs über Rechenfähigkeit und Logik besucht. Das Material enthielt eine Korrelation zwischen Komplexitäts- / Berechenbarkeitsklassen (R, RE, Co-RE, P, NP, Logspace, ...) und Logik (Prädikatenrechnung, Logik erster Ordnung, ...).

Die Korrelation umfasste mehrere Ergebnisse in einem Feld, die unter Verwendung von Techniken aus dem anderen Feld erhalten wurden. Es wurde vermutet, dass P! = NP als ein Problem in der Logik angegriffen werden könnte (indem das Problem von der Domäne der Komplexitätsklassen auf die Logik projiziert wird).

Gibt es eine gute Zusammenfassung dieser Techniken und Ergebnisse?

ripper234
quelle

Antworten:

23

Möglicherweise fragen Sie nach Ergebnissen in der Finiten-Modell-Theorie (wie der Charakterisierung von P und NP anhand verschiedener Fragmente der Logik). Der jüngste Beweisversuch von P! = NP hat sich anfangs stark auf solche Konzepte gestützt, und es gibt einige gute Referenzen (aus dem Wiki )

Suresh Venkat
quelle
Ich denke, der Anwendungsbereich von FMT ist etwas breiter als nur die Verknüpfung von Logik und Rechenkomplexität. Die beschreibende Komplexität scheint ein genauerer Begriff zu sein.
András Salamon
24

Neil Immerman hat ein wunderschönes Diagramm erstellt, das auf einen Blick die Entsprechungen zwischen Komplexitätsklassen und Logik liefert, die von endlichen Modellen interpretiert werden. Es ist auf dem Cover seines Buches und auch am Ende seiner Webseite hier zu finden: http://www.cs.umass.edu/~immerman/

Aaron Sterling
quelle
Dieses Bild sagt mehr als tausend Worte.
András Salamon
5
Immermans Buch ist wahrscheinlich die beste Einzelreferenz für die direkten Verbindungen zwischen Logik und Rechenkomplexität. Dieses Thema wird normalerweise als "Beschreibende Komplexität" bezeichnet, ebenso wie das Buch.
András Salamon
16

Ich kenne zwei Möglichkeiten, Logik mit Komplexitätsklassen zu verknüpfen. Die erste ist die deskriptive Komplexität, die modelltheoretisch in anderen Antworten erwähnt wird. (Zurück zu Ronald Fagins Charakterisierung von )NP

S21

Antonina Kolokolova hat sich mit den Beziehungen zwischen diesen beiden Ansätzen befasst.

Kaveh
quelle
11

Für diejenigen, die mit der Vielzahl der Akronyme in Immermans großem Diagramm nicht vertraut sind, gibt es einen Wikipedia-Artikel zur beschreibenden Komplexität . Es sollte ein Diagramm mit Links geben, damit Sie die Definition direkt in Complexity Zoo und anderen Quellen nachschlagen können. Ich möchte auch besser die Beziehungen zu den entsprechenden formalen Sprachen / Grammatiken sehen und wo Sie den Beweis finden können.

Dies ist keine Antwort, sondern ein Kommentar zu Aarons Antwort, den ich aus irgendeinem Grund nicht kommentieren kann.

Jakob
quelle
Du brauchst etwas mehr Wiederholung, um einen Kommentar zu posten (es ist ein Spam-Blockierungsmechanismus).
Suresh Venkat