## [Largeur de Clause](/fr/node/60892) Définition 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 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 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 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 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 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 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 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 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.