Formal verifizierte Komplexitätstheorie

18

Gibt es ein laufendes Projekt, um die Theoreme und Beweise der Komplexitätstheorie mit einem Beweisassistenten wie Coq formal zu verifizieren? Gibt es dafür Grenzen?

cc.complexity-theory complexity proof-assistants Samuel Schlesinger
quelle
3
Ich glaube, an der Universität von Bologna wird mit dem Proof-Assistenten Matita geforscht. Siehe zum Beispiel Turingmaschinen formalisieren .
Marzio De Biasi
Siehe auch : cstheory.stackexchange.com/q/4052/129 . Einige der Antworten beziehen sich sogar auf Coq, andere auf Ergebnisse, die als theoretische Hindernisse für dieses Projekt interpretiert werden könnten, obwohl dies in der Praxis wahrscheinlich keine Hindernisse sind.
Joshua Grochow
Danke, diese Frage war großartig bei JoshuaGrochow. Ich bin froh, dass ich von dieser Hartmannis-Monographie erfahren habe. Wenn ich das verstehe, würde die Barriere dann sicherstellen, dass die Komplexitätsklassen, die Sie definieren, Ihrer Meinung nach eher sind als die "in Coq nachweisbare" Version.
Samuel Schlesinger
1
Auf eine ähnliche Frage gibt es hier eine Antwort , obwohl es eher darum geht, bestimmte Komplexitätsgrenzen zu beweisen als allgemeine Ergebnisse der Komplexitätstheorie
jmite
Richtig, das ist aber relevant. Ich bin neugierig, wie das zugrunde liegende Typensystem helfen kann, indem es beispielsweise einige Begriffe zur Komplexität in die Funktionstypen einbezieht. Natürlich würde dies zu einer Vielzahl von Gleichheiten führen, aber ich denke, das ist es, was wir natürlich sowieso an Komplexität haben.
Samuel Schlesinger

Antworten:

6

In der folgenden Arbeit stellt mein Kollege Uli Schöpp eine formale Verifikation (in Coq) eines nichttrivialen Ergebnisses von Cook und Rackoff zur Rechenleistung von Graphautomaten vor. https://scholar.google.at/scholar?oi=bibs&cluster=4944920843669159892&btnI=1&hl=de (Schöpp, U. (2008). Eine formalisierte Untergrenze für ungerichtete Erreichbarkeit von Graphen. In Logik für Programmierung, künstliche Intelligenz und Argumentation ( S. 621-635). Springer Berlin / Heidelberg.)

Martin Hofmann
quelle
1
Könnten Sie bitte den vollständigen Verweis angeben, damit die Antwort nicht von der Gültigkeit des Links abhängt?
Feiertag