Interessante Algorithmen zur Formalisierung des Feit-Thompson-Theorems?

26

Es sieht so aus, als hätten George Gonthier und seine Mitarbeiter den Satz der ungeraden Ordnung fertig formalisiert .

In seiner früheren Arbeit zum Vier-Farben-Theorem hat Gonthier eine Reihe neuer Algorithmen (hauptsächlich Varianten von BDDs und Graph-Algorithmen) erfunden, die sich besonders für die formale Verifikation eignen. Ich frage mich, welche neuen algorithmischen Tricks während dieser Entwicklung entwickelt wurden, seit er gesagt hat, dass er diesen kleinräumigen Reflexions- Verifizierungsstil in der Arbeit zur endlichen Gruppentheorie weiter verwendet hat.

lo.logic proof-assistants Neel Krishnaswami
quelle
als Referenz en.wikipedia.org/wiki/Feit%E2%80%93Thompson_theorem (jede endliche Gruppe ungerader Ordnung ist lösbar)
Radu GRIGore
4
Es sollte möglich sein, Gonthier zu veranlassen, diese Fragen zu beantworten. Jemand, der in der Nähe seines Büros ist, zeigt ihn bitte hierher. Sag ihm, wir sind großartige Fans von ihm.
Andrej Bauer
4
Vom Gespräch mit jemandem, der daran gearbeitet hat: Nein. Er hat viele Beweise geschickt verfeinert und viele theoretische Entwicklungen neu strukturiert, aber die beteiligten Algorithmen sind nicht interessant - in der Tat sind viele von ihnen dumme rohe Gewalt, das Gegenteil von interessant.
Jacques Carette
@JacquesCarette: Ich denke, das sollte eine Antwort sein, da sich daran in ein paar Jahren nichts geändert hat ...
Joshua Grochow

Antworten:

10

(Einen Kommentar in eine Antwort verwandeln und erweitern)

Vom Gespräch mit jemandem, der daran gearbeitet hat: Nein. Er erfand alle möglichen cleveren Verfeinerungen für viele Beweise und strukturierte viele theoretische Entwicklungen neu, die beide äußerst wertvoll sind, aber die beteiligten Algorithmen sind nicht interessant - in der Tat sind viele von ihnen dumme rohe Gewalt, das Gegenteil von interessant.

Grundsätzlich wurde nach einer möglichst direkten Verbindung zum Beweis von Feit Thompson gesucht, ohne sich dabei um den „rechnerischen Inhalt“ zu kümmern (und ohne sich übermäßig um die Wiederverwendbarkeit einiger Module zu sorgen). Dies war in Anbetracht des Zeitplans bereits äußerst ehrgeizig. Glücklicherweise haben einige der an dem Projekt beteiligten Personen viele Teile der zu erstellenden Beweise überarbeitet

  • Mehrfachverwendbarkeit für eine größere Anzahl von Anwendungen
  • rechenintensiver
Jacques Carette
quelle