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.