Le nombre maximum de littéraux présents dans une seule clause d'un ensemble de clauses ; souvent appelé taille de clause dans les analyses combinatoires.

Principe

Prendre la longueur maximale d'une clause comme borne sur la complexité locale de disjonction ; la résolution et les bornes combinatoires évoluent souvent avec la largeur.

Démonstration

Dans la CNF { (x1 ∨ x2), (¬x1 ∨ x3 ∨ x4), (x2) } les largeurs de clause sont 2, 3 et 1, donc la Largeur De Clause est 3.

Mauvaise application

Remplacer la Largeur De Clause par la taille moyenne ou la médiane des clauses décrit mal le comportement combinatoire pire-cas utilisé dans de nombreuses preuves.

Conséquence

Une faible Largeur De Clause fixe peut entraîner des garanties de complexité plus fortes (par exemple, bornes en résolution de largeur bornée) et permettre des algorithmes spécialisés.

Inversion

Considérer la largeur minimale des clauses se concentre sur les clauses les plus faciles à satisfaire mais ignore les clauses qui déterminent le branchement pire-cas de la recherche.

Limite

Défini pour les représentations clausales (CNF) ; ne se transpose pas directement aux formules non clausales sans conversion en clauses et exclut les mesures de multiplicité des littéraux à l'intérieur des clauses.

Tension sémantique

Tension avec le Nombre De Littéraux et la Densité De Clauses : deux instances ayant la même Largeur De Clause peuvent se comporter différemment selon que l'une contient de nombreuses clauses larges répétées et l'autre une seule clause large.

Synthèse

La Largeur De Clause saisit la taille disjonctive pire-cas au niveau d'une clause au sein d'un ensemble ; c'est une borne structurelle locale utilisée pour contrôler les analyses de complexité combinatoire et de preuve.