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

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

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

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

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

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

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

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

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.