##  [Klauseldichte](/de/node/60894) 

 Definition

Das Verhältnis der Anzahl der Klauseln (m) zur Anzahl der propositionalen Variablen (n) in einer CNF-Instanz, üblicherweise als m/n angegeben.

 

 

 

 

 

 





## Prinzip

Prinzip

Erfasst globale Sparsität oder Klauseleng mit Normierung der Klauselanzahl durch Variablenanzahl; dient als Steuerparameter für empirische Härte und phasenähnliches Verhalten.

 

 

 

 

 





## Demonstration

Demonstration

Eine 3-SAT-Instanz mit 450 Klauseln über 100 Variablen hat eine Klauseldichte von 450/100 = 4,5, was sie in Bereiche einordnet, in denen sich die empirische Schwierigkeit oft ändert.

 

 

 

 

## Fehlanwendung

Fehlanwendung

Die Klauseldichte anzuwenden, ohne Heterogenität der Klausellängen, Klauselwiederholungen oder die Verteilung der Variablenfrequenzen zu berücksichtigen, kann die tatsächliche Schwierigkeit falsch vorhersagen.

 

 

 

 

 





## Konsequenz

Konsequenz

Wird verwendet, um Instanzfamilien zu schichten und Bereiche der Erfüllbarkeit/Unerfüllbarkeit sowie die Leistung von Lösern vorherzusagen; bestimmte Dichten korrelieren mit höherem empirischem Suchaufwand.

 

 

 

 

## Umkehrung

Umkehrung

Dichte als absolute Schwierigkeit zu interpretieren, ignoriert strukturelle Merkmale: Eine dichte Instanz kann einfach sein, wenn Klauseln redundant sind oder wenn es ein kleines Backdoor zu einer lösbaren Klasse gibt.

 

 

 

 

 





## Abgrenzung

Abgrenzung

Definiert für propositionale CNF, bei der Klausel- und Variablenanzahlen eindeutig sind; nicht direkt anwendbar auf quantifizierte Formeln, gewichtete SAT-Varianten oder nicht-klausale Kodierungen ohne Anpassung.

 

 

 

 

 





## Semantische Spannung

Semantische Spannung

Spannung mit Backdoor-Setgröße und Klauselbreite: Ähnliche Dichten können sehr unterschiedliche Härten erzeugen, abhängig von struktureller Zerlegbarkeit oder Klauselaritäten.

 

 

 

 

 





## Synthese

Synthese

Die Klauseldichte ist eine normalisierte globale Statistik m/n, die die Dichte der Nebenbedingungen pro Variable zusammenfasst; sie ist ein nützlicher heuristischer Parameter zur Vorhersage empirischer Schwierigkeit, muss aber zusammen mit Strukturmaßen interpretiert werden.