The ratio of the number of clauses (m) to the number of propositional variables (n) in a CNF instance, commonly expressed as m/n.

Principle

Capture global sparsity or constraint tightness by normalizing clause count by variable count; serves as a control parameter for empirical hardness and phase-like behavior.

Demonstration

A 3-SAT instance with 450 clauses over 100 variables has Clause Density 450/100 = 4.5, which situates it relative to regimes where empirical difficulty often changes.

Misapplication

Applying Clause Density without accounting for clause length heterogeneity, clause repetition, or variable frequency distribution can mispredict actual instance difficulty.

Consequence

Used to stratify instance families and predict regimes of satisfiability/unsatisfiability and solver performance; certain densities correlate with higher empirical search cost.

Reversal

Interpreting density as absolute difficulty ignores structural features: a high-density instance can be easy if clauses are redundant or if there is a small backdoor to a tractable class.

Boundary

Defined for propositional CNF where clause and variable counts are well-defined; not directly applicable to quantified formulas, weighted SAT variants, or non-clausal encodings without adaptation.

Semantic Tension

Tension with Backdoor Set Size and Clause Width: similar densities can produce very different hardness depending on structural decomposability or clause arities.

Synthesis

Clause Density is a normalized global statistic m/n that summarizes constraint abundance per variable; it is a useful heuristic parameter for predicting empirical difficulty but must be interpreted alongside structural measures.