##  [Klauselbreite](/de/node/60892) 

 Definition

Die maximale Anzahl von Literalen, die in einer einzelnen Klausel einer Klauselmenge vorkommen; in der Kombinatorik oft als Klauselgröße bezeichnet.

 

 

 

 

 

 





## Prinzip

Prinzip

Die größte Klausellänge als Schranke für die lokale Disjunktionskomplexität verwenden; Resolution und kombinatorische Schranken skalieren häufig mit der Breite.

 

 

 

 

 





## Demonstration

Demonstration

In der CNF { (x1 ∨ x2), (¬x1 ∨ x3 ∨ x4), (x2) } sind die Klauselbreiten 2, 3 und 1, daher ist die Klauselbreite 3.

 

 

 

 

## Fehlanwendung

Fehlanwendung

Die Klauselbreite durch mittlere oder mediane Klauselgröße zu ersetzen verfälscht das worst-case-kombinatorische Verhalten, das in vielen Beweisen verwendet wird.

 

 

 

 

 





## Konsequenz

Konsequenz

Eine kleine feste Klauselbreite kann stärkere Komplexitätsgarantien liefern (z. B. Schranken für die Resolution mit beschränkter Breite) und spezialisierte Algorithmen ermöglichen.

 

 

 

 

## Umkehrung

Umkehrung

Die Betrachtung der minimalen Klauselbreite fokussiert auf leicht erfüllbare Klauseln, ignoriert jedoch die Klauseln, die das worst-case-Verzweigungsverhalten bestimmen.

 

 

 

 

 





## Abgrenzung

Abgrenzung

Definiert für klausale (CNF) Darstellungen; lässt sich nicht ohne Klauselkonversion direkt auf nicht-klausale Formeln übertragen und schließt Maße der Literalvielfachheit innerhalb von Klauseln aus.

 

 

 

 

 





## Semantische Spannung

Semantische Spannung

Spannung mit der Anzahl Der Literale und der Klauseldichte: Zwei Instanzen mit gleicher Klauselbreite können sich sehr unterschiedlich verhalten, wenn die eine viele breite Klauseln wiederholt, die andere nur eine breite Klausel hat.

 

 

 

 

 





## Synthese

Synthese

Die Klauselbreite erfasst die worst-case-Disjunktionsgröße einer einzelnen Klausel in einer Klauselmenge; sie ist eine lokale strukturelle Schranke zur Steuerung von kombinatorischen und Beweiskomplexitätsanalysen.