El número máximo de literales que aparecen en una única cláusula de un conjunto de cláusulas; a menudo llamado tamaño de cláusula en análisis combinatorios.

Principio

Usar la longitud máxima de cláusula como cota de la complejidad local de disyunción; la resolución y las cotas combinatorias suelen escalar con la anchura.

Demostración

En la CNF { (x1 ∨ x2), (¬x1 ∨ x3 ∨ x4), (x2) } las anchuras de cláusula son 2, 3 y 1, por lo que la Anchura De Cláusula es 3.

Aplicación incorrecta

Sustituir la Anchura De Cláusula por la media o la mediana de tamaños de cláusula caracteriza mal el comportamiento combinatorio en el peor caso usado en muchas demostraciones.

Consecuencia

Una Anchura De Cláusula pequeña y fija puede dar garantías de complejidad más fuertes (por ejemplo, cotas para resolución de anchura acotada) y permitir algoritmos especializados.

Inversión

Considerar la anchura mínima de cláusula se centra en las cláusulas más fáciles de satisfacer pero ignora las cláusulas que determinan el ramificado en el peor caso de la búsqueda.

Límite

Definido para representaciones clausales (CNF); no se traslada directamente a fórmulas no clausales sin conversión a cláusulas y excluye medidas de multiplicidad de literales dentro de cláusulas.

Tensión semántica

Tensión con el Conteo De Literales y la Densidad De Cláusulas: dos instancias con la misma anchura pueden comportarse muy distinto si una tiene muchas cláusulas anchas repetidas y la otra solo una cláusula ancha.

Síntesis

La Anchura De Cláusula captura el tamaño disyuntivo peor-caso a nivel de cláusula dentro de un conjunto; es una cota estructural local usada para controlar análisis de complejidad combinatoria y de prueba.