Gibt es ein Typsystem, das die Lambda-Begriffe auf die Begriffe beschränkt, die in eine Komplexitätsklasse fallen? Wie liegen die typisierbaren Begriffe in der Theorie streng innerhalb der Komplexitätsklasse? Oder ist das überhaupt nicht möglich?
Ich finde, es gibt viele Studien zur Expressibilität der Typentheorie, wie nachweislich terminierende, erweiterte Polynome usw. Aber gibt es eine Möglichkeit, dies auf eine Komplexitätsklasse zu beschränken?
complexity-classes
type-theory
Vinothkumar Raman
quelle
quelle
Antworten:
Die Schlüsselwörter, nach denen Sie suchen, sind "Implizite Computerkomplexität". Die Feldstudien zum Beispiel Varianten der linearen Logik und die Komplexitätsgrenzen, die sie für die den Ableitungen zugrunde liegenden Begriffe garantieren können.
quelle