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. Q060 — Donner un CSP binaire arc-cohérent mais insatisfiable, avec domaines et contraintes explicites.
Je vous remercie pour cette question, qui porte sur un point classique de la théorie des contraintes.
## Réponse
Un CSP binaire arc-cohérent mais insatisfiable est un problème où chaque contrainte binaire est cohérente pour chaque valeur de chaque domaine (toute valeur possède au moins un support dans l'autre domaine), et pourtant aucune affectation complète ne satisfait toutes les contraintes simultanément.
Voici un exemple explicite, le plus simple possible.
Variables et domaines :
- X ∈ {1, 2}
- Y ∈ {1, 2}
- Z ∈ {1, 2}
Contraintes binaires :
- C_XY : X ≠ Y
- C_YZ : Y ≠ Z
- C_XZ : X ≠ Z
Vérification de l'arc-cohérence :
Pour chaque valeur de chaque variable, il existe un support dans le domaine de l'autre variable de chaque contrainte :
- Pour X = 1 : support Y = 2 dans C_XY, et support Z = 2 dans C_XZ.
- Pour X = 2 : support Y = 1 dans C_XY, et support Z = 1 dans C_XZ.
- Pour Y = 1 : support X = 2 dans C_XY, et support Z = 2 dans C_YZ.
- Pour Y = 2 : support X = 1 dans C_XY, et support Z = 1 dans C_YZ.
- Pour Z = 1 : support X = 2 dans C_XZ, et support Y = 2 dans C_YZ.
- Pour Z = 2 : support X = 1 dans C_XZ, et support Y = 1 dans C_YZ.
Le CSP est donc bien arc-cohérent : aucune valeur n'est éliminable par filtrage d'arc.
Insatisfiabilité :
Les trois contraintes imposent que X, Y et Z soient deux à deux distincts. Or les domaines ne contiennent que deux valeurs. Par le principe des tiroirs, trois variables ne peuvent pas prendre trois valeurs distinctes parmi deux valeurs possibles. Aucune affectation complète ne satisfait les trois contraintes à la fois.
On peut le vérifier par énumération : toute affectation de X et Y avec X ≠ Y utilise les deux valeurs {1, 2} ; alors Z doit être différent de X et de Y simultanément, ce qui est impossible puisque Z ne peut prendre que 1 ou 2, déjà tous deux utilisés.
## Justification
Cet exemple illustre précisément la limite de l'arc-cohérence : c'est une propriété locale (par paire de variables) qui ne capture pas les interactions globales entre trois variables ou plus. L'insatisfiabilité ici provient d'un cycle de contraintes (X–Y–Z–X) dont la cohérence locale ne suffit pas à garantir la cohérence globale. C'est un cas d'école bien connu, souvent présenté comme le plus petit exemple de CSP arc-cohérent insatisfiable.
Confiance : 97 %. La construction est standard et vérifiée point par point ci-dessus ; la vérification exhaustive est ici complète et sans ambiguïté, et la seule réserve tient à la formulation canonique de l'exemple, que je présente de mémoire.
Je reste à votre disposition pour approfondir, par exemple sur les notions de cohérence de chemin ou de k-cohérence qui résolvent ce type de limitation.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.