La relación entre el número de cláusulas (m) y el número de variables proposicionales (n) en una instancia CNF, comúnmente expresada como m/n.

Principio

Capturar la esparsidad global o la densidad de restricciones normalizando el número de cláusulas por el número de variables; actúa como parámetro que controla la dureza empírica y comportamientos tipo fase.

Demostración

Una instancia 3-SAT con 450 cláusulas sobre 100 variables tiene Densidad De Cláusulas 450/100 = 4,5, lo que la sitúa en regímenes donde la dificultad empírica suele cambiar.

Aplicación incorrecta

Aplicar la Densidad De Cláusulas sin tener en cuenta la heterogeneidad de longitudes de cláusula, repeticiones de cláusulas o la distribución de frecuencias de variables puede predecir mal la dificultad real.

Consecuencia

Se utiliza para estratificar familias de instancias y predecir regímenes de satisfacibilidad/insatisfacibilidad y rendimiento de solucionadores; ciertas densidades se correlacionan con costes de búsqueda empíricos mayores.

Inversión

Interpretar la densidad como dificultad absoluta ignora rasgos estructurales: una instancia de alta densidad puede ser fácil si las cláusulas son redundantes o existe un pequeño backdoor hacia una clase tratable.

Límite

Definida para CNF proposicional donde los recuentos de cláusulas y variables son bien definidos; no es aplicable directamente a fórmulas cuantificadas, variantes SAT ponderadas o codificaciones no clausales sin adaptación.

Tensión semántica

Tensión con el Tamaño Del Conjunto Backdoor y la Anchura De Cláusula: densidades similares pueden producir durezas muy distintas según la descomponibilidad estructural o la aridad de cláusulas.

Síntesis

La Densidad De Cláusulas es una estadística global normalizada m/n que resume la abundancia de restricciones por variable; es un parámetro heurístico útil para predecir dificultad empírica pero debe interpretarse junto con medidas estructurales.