INSTRUCTIONS AU MODÈLE - Répondre sans outil externe ni Internet. - Pour chaque question, fournir la réponse, une justification suffisante et une confiance de 0 à 100 %. - Ne jamais inventer une donnée, une référence, un DOI ou un résultat absent. - Signaler explicitement les prémisses fausses, les informations insuffisantes et les cas indéterminables. - Vérifier numériquement ou symboliquement les contre-exemples proposés. - Chaque question est indépendante, sauf indication explicite contraire. Q059 — Définir la strong k-consistency et la distinguer de la simple k-consistency.
Je vous remercie pour cette question portant sur la théorie des contraintes. Voici l’analyse demandée.
**Définition de la k-consistency simple**
Un réseau de contraintes est dit k-consistant si, pour tout ensemble de k−1 variables dont les valeurs sont toutes compatibles entre elles, c’est-à-dire satisfont toutes les contraintes portant sur ces variables, il existe une valeur pour toute k‑ième variable telle que l’ensemble des k variables satisfasse toutes les contraintes qui les relient. Autrement dit, la k‑consistency garantit que toute solution partielle portant sur k−1 variables peut être étendue à une solution partielle portant sur k variables. La 1‑consistency correspond à la node consistency, chaque domaine étant non vide, et la 2‑consistency à l’arc consistency.
**Définition de la strong k-consistency**
Un réseau de contraintes est fortement k‑consistant s’il est j‑consistant pour tout j allant de 1 à k. La strong k‑consistency est donc une propriété cumulative : elle exige que le réseau soit simultanément 1‑consistant, 2‑consistant, et ainsi de suite jusqu’à k‑consistant.
**Distinction essentielle**
La différence est fondamentale. La simple k‑consistency est une propriété locale portant uniquement sur les ensembles de k variables : elle ne dit rien sur les sous‑ensembles plus petits. Un réseau peut être 3‑consistant sans être 2‑consistant, par exemple. La strong k‑consistency, elle, impose la propriété à tous les niveaux inférieurs, ce qui en fait une propriété beaucoup plus exigeante et structurellement plus utile.
**Intérêt de la strong k-consistency**
L’intérêt théorique majeur est le suivant : un réseau fortement k‑consistant et dont le graphe a une largeur inférieure à k est globalement consistant, c’est‑à‑dire que toute solution partielle s’étend en une solution complète. Ce résultat, dû à Freuder, explique pourquoi la strong k‑consistency est la notion pertinente pour raisonner sur la résolution de réseaux de contraintes, alors que la simple k‑consistency, prise isolément, ne suffit pas à garantir de telles propriétés globales.
**Exemple illustratif**
Considérons un réseau à trois variables X, Y, Z, chacune à domaine {0, 1}, avec la contrainte X ≠ Y. Ce réseau est 2‑consistant : pour toute valeur de X, il existe une valeur de Y satisfaisant la contrainte, et réciproquement. Il est aussi 1‑consistant. En revanche, il n’est pas 3‑consistant, car il n’existe aucune contrainte portant sur Z, et pourtant la définition de la 3‑consistance exigerait que toute paire de valeurs compatibles sur deux variables puisse s’étendre à une troisième variable — ce qui est trivialement satisfait ici puisque Z est libre. En réalité, ce réseau est bien 3‑consistant. Un meilleur contre‑exemple serait un réseau où une contrainte binaire est satisfaite pour certaines paires mais où l’extension échoue. Prenons X, Y, Z à domaines {0, 1}, avec X ≠ Y et Y ≠ Z. Ce réseau est 2‑consistant et 1‑consistant. Est‑il 3‑consistant ? Prenons X = 0, Y = 1, compatible. Il faut une valeur de Z telle que Y ≠ Z, donc Z = 0, ce qui est possible. Prenons X = 1, Y = 0, alors Z = 1 convient. Le réseau est donc 3‑consistant. Pour obtenir un réseau 2‑consistant mais non 3‑consistant, il faut une contrainte ternaire. Considérons X, Y, Z à domaines {0, 1} avec la contrainte ternaire X + Y + Z = 0 en arithmétique entière. Toute paire de valeurs sur deux variables s’étend : par exemple X = 0, Y = 0 impose Z = 0, possible ; X = 0, Y = 1 impose Z = −1, impossible. Le réseau n’est donc pas 3‑consistant. Il est en revanche 2‑consistant, car toute valeur d’une variable s’étend à une autre, et 1‑consistant. Ce réseau est donc 2‑consistant mais pas 3‑consistant, illustrant qu’une k‑consistency simple n’implique pas les niveaux inférieurs ni supérieurs. Il n’est pas fortement 3‑consistant, puisqu’il n’est pas 3‑consistant.
**Confiance**
Je formule cette réponse avec une confiance de 92 %. Les définitions de la k‑consistency et de la strong k‑consistency sont des notions standard de la théorie des réseaux de contraintes, et le résultat de Freuder reliant strong k‑consistency et largeur de graphe est un théorème classique. Ma confiance n’est pas plus élevée car je récite ces définitions de mémoire, sans pouvoir vérifier ici la formulation canonique exacte dans la littérature, et l’exemple numérique que je propose, bien que vérifié, est de ma construction.
Je reste à votre disposition pour approfondir, par exemple sur les algorithmes d’établissement de la strong k‑consistency ou sur les liens avec la décomposition de graphes.Resultat fige a la premiere execution, directement depuis le service public LANXAS White, sans intervention manuelle. Cette page est permanente et peut etre re-consultee pour verification.