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?
cc.complexity-theory
lo.logic
computability
ripper234
quelle
quelle
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/
quelle
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
Antonina Kolokolova hat sich mit den Beziehungen zwischen diesen beiden Ansätzen befasst.
quelle
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.
quelle