Verwenden Sie die Lambda-Berechnung, um die Zeitkomplexität abzuleiten?

Gibt es irgendwelche Vorteile bei der Berechnung der zeitlichen Komplexität eines Algorithmus unter Verwendung der Lambda-Berechnung? Oder gibt es ein anderes System für diesen Zweck?

Alle Referenzen wäre dankbar.

Ohad hat vollkommen recht mit den Problemen, mit denen die Lambda-Rechnung als Grundlage für die Diskussion über Komplexitätsklassen konfrontiert ist. Es wurde einiges an Arbeit geleistet, um die Komplexität der Reduzierbarkeit im Lambda-Kalkül zu charakterisieren, insbesondere im Zusammenhang mit der Arbeit an gekennzeichneten und optimalen Reduktionen aus Lèvys Doktorarbeit. Grundsätzlich sollten gute Kostenmodelle für die Lambda-Berechnung nicht allen Beta-Reduktionen eine konstante Gewichtung zuweisen: Intuitiv sollte das Einsetzen eines großen Subterms in viele Orte mit unterschiedlichem Umfang mehr kosten als das Einsetzen eines kleinen K-Redex, und wenn man einen bestimmten Betrag möchte Dies ist für die Invarianz der Kosten unter verschiedenen Umschreibestrategien von wesentlicher Bedeutung.

Zwei Links:

1. Lawall & Mairson, 1996, Optimalität und Ineffizienz: Was ist kein Kostenmodell der Lambda-Rechnung? (.ps.gz) - Grundlegender Überblick über Fragen, die sich auf die Wahl des Kostenmodells auswirken , und warum viele plausible Ideen nicht funktionieren.
2. Dal Lago & Martini, 2008, Der schwache Lambda-Kalkül als vernünftige Maschine - Bietet ein Kostenmodell für den Call-by-Value-Lambda-Kalkül zusammen mit einer guten Diskussion der Literatur.

Es gibt quantitative Ergebnisse bezüglich des Kalküls in Form der Messung der Länge der Verringerungen des (typisierten) Lambda-Kalküls. Dies sagt jedoch noch lange nichts über die Komplexität der Algorithmen aus (insbesondere, dass die erzielten Grenzen schnell wachsen). Siehe zum Beispiel: Arnold Beckmann, Genaue Schranken für Reduktionslängen in typisiertem Kalkül, Journal of Symbolic Logic 2001, 66 (3): 1277-1285.$\lambda$$\lambda$

Für etwas näheres zu Ihrer Frage gibt es ein aktuelles Projekt, das ein Typensystem (eine funktionale Programmiersprache) entwickelt und untersucht, das durch statische Analyse (polynomielle) Laufzeitgrenzen von Programmen (sowie andere von verwendeten Ressourcen) bestimmen kann Programme). In gewissem Sinne könnte dies darauf hindeuten, dass die Verwendung der funktionalen Programmierung zur Analyse der Laufzeitkomplexität von Vorteil sein könnte. Die Projekthomepage ist hier .

Ein möglicherweise repräsentativer Beitrag zu diesem Projekt ist: Jan Hoffmann, Martin Hofmann. Amortisierte Ressourcenanalyse mit Polynompotential - eine statische Folgerung von Polynomgrenzen für funktionale Programme. In Proceedings of the 19th European Symposium on Programming (ESOP'10). Verknüpfung

Eine aktuelle Entwicklung zu diesem Thema: U. dal Lago und B. Accatoli haben bewiesen, dass die Länge der äußersten linken Reduktion (LOr) eines Term ein invariantes (Zeit-) Kostenmodell für Kalkül ist.$\lambda$$\lambda$

Sie zeigen, dass Turing-Maschinen (mit cost = time) und Terme (mit cost = length of the LOr) sich mit einem zeitlichen Polynom-Overhead simulieren können. So hängt beispielsweise die Definition der Klasse P nicht davon ab, welches der beiden Berechnungsmodelle Sie verwenden, um es zu definieren.$\lambda$

http://arxiv.org/abs/1405.3311

Es gibt eine sehr interessante, auf linearer Logik basierende Linie, die implizite Komplexitätstheorie, die verschiedene Komplexitätsklassen charakterisiert, indem sie dem Lambda-Kalkül verschiedene Typdisziplinen auferlegt. IIRC, diese Arbeit begann, als Bellantoni und Cook, und Leivant herausfanden, wie man das Typensystem verwendet, um die primitive Rekursion zu binden, um verschiedene Komplexitätsklassen zu erfassen.

Im Allgemeinen liegt der Reiz der Arbeit mit Lambda-Kalkülen darin, dass es manchmal möglich ist, erweiterte (dh mathematisch besser nachvollziehbare) Charakterisierungen verschiedener Intensionsmerkmale zu finden, die Modellen wie Turing-Maschinen ihre Kraft verleihen. Ein Unterschied zwischen Turing-Maschinen und reinem Lambda-Kalkül besteht beispielsweise darin, dass ein Client, da Turing Programmcodes empfängt, manuell Zeitüberschreitungen implementieren kann, um eine Schwalbenschwanzbildung zu implementieren - und daher Parallel- oder Berechnungen durchführen kann. Timeouts können jedoch auch metrisch modelliert werden, und Escardo hat vermutet (ich kenne seinen Status nicht), dass metrische Raummodelle des Lambda-Kalküls für PCF + -Timeouts vollständig abstrakt sind. Metrische Räume sind sehr gut untersuchte mathematische Objekte, und es ist sehr schön, diese Theorie anwenden zu können.

Die Schwierigkeit bei der Verwendung der Lambda-Berechnung besteht jedoch darin, dass Sie gezwungen sind, Phänomene höherer Ordnung direkt vom Startgatter aus zu betrachten. Dies kann sehr subtil sein, da die Church-Turing-These bei höherem Typ versagt - natürliche Berechnungsmodelle unterscheiden sich bei höherem Typ, da sie sich darin unterscheiden, was Sie mit den Darstellungen von Berechnungen tun dürfen. (Parallel-or ist ein einfaches Beispiel für dieses Phänomen, da es einen Unterschied zwischen LC und TM aufweist.) Darüber hinaus gibt es nicht einmal eine strikte Einbeziehung zwischen den verschiedenen Modellen, da die Kontravarianz des Funktionsraums zu einer stärkeren Ausdruckskraft führt bei einer Ordnung bedeutet weniger Ausdruckskraft eine Ordnung höher.

Soweit ich weiß, ist die Lambda-Rechnung für diesen Zweck schlecht geeignet, da der Begriff der zeitlichen / räumlichen Komplexität in der Lambda-Rechnung schwer zu formulieren ist.

Was ist 1 Zeiteinheit Komplexität? Eine Beta-Reduktion? Was ist mit den Einheiten der Raumkomplexität? Die Länge der Zeichenfolge?

Die Lambda-Rechnung eignet sich eher zur abstrakten Manipulation von Algorithmen, da sie sich viel leichter komponieren lässt als Turing-Maschinen.

Sie können auch explizite Substitutionskalküle nachschlagen, die die Meta-Level-Substitution des Lambda-Kalküls in eine Reihe expliziter Reduktionsschritte aufteilen. Dies berührt Charles 'Standpunkt, dass unter Berücksichtigung der zeitlichen Komplexität nicht alle Substitutionen als gleich angesehen werden sollten.

Siehe Nils Anders Danielsson, Semiformale Zeitkomplexitätsanalyse für rein funktionale Datenstrukturen, die als Bibliothek in Agda implementiert ist. Sehr vielversprechend sehen auch die Zitate aus dem Papier aus.

Eine wichtige Erkenntnis für mich ist, dass es angemessen / nützlich / vernünftig / halbautomatisch ist, die zeitliche Komplexität von Algorithmen im einfach getippten Lambda-Kalkül abzuleiten, insbesondere wenn diese Algorithmen darin leicht ausdrückbar sind (dh rein funktional sind) und ganz besonders, wenn diese Algorithmen nutzen wesentlich zB die Call-by-Name-Semantik. Zusammen mit diesem ist der wahrscheinlich offensichtliche Punkt, dass man Komplexität nicht nur "im Lambda-Kalkül" berechnet, sondern im Lambda-Kalkül unter einer gegebenen Bewertungsstrategie.