##  [Beweislänge](/de/node/60902) 

 Definition

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

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

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

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

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

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

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

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

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.