Die Anzahl der Inferenzschritte in einer formalen Ableitung oder Beweis innerhalb eines bestimmten Beweissystems; jeder Schritt ist die Anwendung einer Regel, die aus vorherigen Formeln oder Sequenzen eine neue erzeugt.

Prinzip

Zählt den sequentiellen inferentiellen Aufwand: kürzere Beweise minimieren die Anzahl der Regelanwendungen, die benötigt werden, um eine Zielformel aus Prämissen oder Axiomen im gewählten formalen System herzuleiten.

Demonstration

Bei der aussagenlogischen Resolution ist die Beweislänge die Anzahl der Resolution- oder Abschwächungsschritte, die durchgeführt werden, bis die leere Klausel (Widerlegung) abgeleitet ist, unabhängig von der Größe der Zwischenklauseln.

Fehlanwendung

Die Beweislänge systemübergreifend oder über Kodierungen hinweg ohne Normierung zu verwenden, kann irreführend sein — einige Systeme erlauben viele kleine lokale Schritte, andere wenige mächtige Regeln, wodurch rohe Zählungen nicht vergleichbar sind.

Konsequenz

Untere Schranken für die Beweislänge etablieren Härteresultate für automatische Beweiser in diesem System; das Finden kurzer Beweise ermöglicht schnellere Verifikation und kann Suchheuristiken leiten, prägnante Ableitungen zu bevorzugen.

Umkehrung

Man kann den Fokus umkehren und stattdessen die symbolische Größe messen (Beweisgröße in der Gesamtanzahl der Symbole oder Bits), was die Formelkomplexität pro Schritt betont statt der Schrittanzahl.

Abgrenzung

Definiert relativ zu einem spezifischen Beweissystem, der Wahl primitiver Regeln und der Granularität dessen, was als Schritt zählt; schließt Ressourcen wie Speichernutzung pro Schritt aus und spiegelt möglicherweise nicht parallele Inferenzen wider.

Semantische Spannung

Steht im Spannungsverhältnis zu Breiten- und Raummaßen: Ein Beweis kann kurz, aber breit oder raumintensiv sein, sodass Länge allein nicht alle Komplexitätsaspekte erfasst.

Synthese

Beweislänge ist ein lineares Maß für inferentiellen Aufwand in einem formalen System; zusammen mit Breite- und Raummaßen liefert sie ein mehrdimensionales Bild der Beweiskomplexität und informiert algorithmische Entscheidungen über Trade-offs zwischen vielen kleinen Schritten und wenigen komplexen Regeln.