LANXAS White, Blind Benchmark v2.0, liasse v2-051 à v2-060

Liasse de consultation : copie conforme, octet pour octet, des exécutions gelées du 21 août 2026. Les pages individuelles test-v2-NNN.html restent la référence opposable, chaque réponse est vérifiable par son SHA-256. Aucune ré-exécution, aucune modification.

Index des 12 liasses · Registre officiel

Copie v2-051

Question (verbatim)

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.

Q051 — Écrire l’invariant de boucle permettant de prouver la correction de la recherche binaire.

Réponse intégrale (verbatim, hachée ci-dessus)

Madame, Monsieur,

Je vous remercie de cette question portant sur la preuve de correction de la recherche binaire. Voici l'invariant de boucle permettant d'établir cette correction, avec sa justification complète.

L'invariant de boucle classique pour la recherche binaire s'énonce ainsi, en supposant que l'on cherche une valeur x dans un tableau T trié par ordre croissant, indicé de 0 à n-1, avec deux bornes g (gauche) et d (droite) telles que la zone de recherche soit l'intervalle [g, d] :

Invariant : à chaque itération, si x est présent dans le tableau, alors il se trouve dans l'intervalle [g, d]. Autrement dit, x n'est ni strictement avant g, ni strictement après d.

Formellement, pour tout indice i :
- si i < g, alors T[i] < x ;
- si i > d, alors T[i] > x.

Justification de la correction :

Initialisation. Avant la première itération, on pose g = 0 et d = n-1. L'intervalle couvre tout le tableau, donc l'invariant est trivialement vrai : si x est présent, il est bien dans [0, n-1].

Conservation. On calcule m = (g + d) / 2 (division entière). Trois cas :
- si T[m] = x, on a trouvé la valeur, l'algorithme se termine correctement ;
- si T[m] < x, alors, comme le tableau est trié, tous les éléments d'indice inférieur ou égal à m sont strictement inférieurs à x. On pose g = m + 1, et l'invariant reste vrai : x ne peut être qu'à droite de m ;
- si T[m] > x, tous les éléments d'indice supérieur ou égal à m sont strictement supérieurs à x. On pose d = m - 1, et l'invariant reste vrai : x ne peut être qu'à gauche de m.

Dans tous les cas, l'invariant est préservé d'une itération à la suivante.

Terminaison. À chaque itération, la taille de l'intervalle d - g + 1 diminue strictement (puisque l'on exclut toujours m), donc la boucle se termine.

Conclusion. À la sortie de la boucle, on a g > d, c'est-à-dire un intervalle vide. L'invariant affirme alors que si x était présent, il serait dans un intervalle vide, ce qui est impossible. On en déduit que x est absent du tableau, et l'algorithme renvoie correctement l'échec. Si au contraire on a rencontré T[m] = x en cours de route, la valeur a été correctement localisée.

Cet invariant est la clé de la preuve : il exprime précisément que la zone de recherche contient toujours la cible si elle existe, et la décroissance de l'intervalle garantit la terminaison.

Confiance : 97 %. Il s'agit d'un résultat standard et bien établi de l'algorithmique ; la seule marge d'incertitude tient aux variantes de formulation (bornes incluses ou exclues, choix de la division entière), qui ne changent pas le principe mais peuvent modifier les détails de l'énoncé.

Je vous prie d'agréer, Madame, Monsieur, l'expression de mes salutations distinguées.

Copie v2-052

Question (verbatim)

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.

Q052 — Un tri stable conserve-t-il l’ordre relatif des éléments de clés égales ?

Réponse intégrale (verbatim, hachée ci-dessus)

Bonjour,

Oui, c'est exactement la définition d'un tri stable.

Un algorithme de tri est dit stable lorsque, pour deux éléments quelconques possédant des clés égales, leur ordre relatif dans la séquence de sortie est identique à celui qu'ils avaient dans la séquence d'entrée. Autrement dit, si un élément A précède un élément B dans la donnée initiale et que leurs clés sont égales, alors A précède encore B après le tri.

Cette propriété est précieuse en pratique : elle permet de trier selon plusieurs critères successifs. Par exemple, on peut d'abord trier une liste de personnes par nom, puis la trier par âge avec un tri stable : les personnes de même âge resteront alors classées par ordre alphabétique, car le second tri préserve l'ordre établi par le premier.

Parmi les tris classiques, le tri à bulles, le tri par insertion et le tri fusion sont stables, tandis que le tri rapide (quicksort) et le tri par tas (heapsort) ne le sont pas dans leurs implémentations usuelles.

Confiance : 97 %. Cette affirmation est une définition standard de l'informatique, vérifiable dans tout manuel d'algorithmique ; je laisse une petite marge uniquement par principe de calibration, la notion étant parfaitement établie.

Cordialement.

Copie v2-053

Question (verbatim)

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.

Q053 — Pourquoi counting sort n’est-il pas un tri par comparaison ? Donner sa complexité en fonction de n et de l’étendue k.

Réponse intégrale (verbatim, hachée ci-dessus)

Je vous remercie pour cette question, que je vais traiter avec la rigueur qu'elle mérite.

Pourquoi counting sort n'est pas un tri par comparaison

Un tri par comparaison est un algorithme dont le comportement repose exclusivement sur des opérations de comparaison entre éléments, du type « a est-il inférieur à b ? ». La borne inférieure classique de Ω(n log n) pour ces tris découle précisément de cette restriction : avec n éléments, il existe n! permutations possibles, et chaque comparaison binaire ne peut au mieux éliminer que la moitié des cas restants, d'où un nombre minimal de comparaisons de l'ordre de log₂(n!).

Counting sort, lui, n'effectue aucune comparaison entre les éléments à trier. Il exploite directement la valeur numérique des clés pour les compter et les placer. Son fonctionnement se décompose en trois phases : il compte d'abord le nombre d'occurrences de chaque valeur possible dans l'intervalle [0, k−1], puis il transforme ces comptages en positions cumulées, enfin il reconstruit le tableau trié en plaçant chaque élément à sa position définitive. Aucune de ces étapes ne compare deux éléments entre eux ; on compare seulement les clés à des bornes d'index, ce qui n'est pas une comparaison entre éléments. C'est pourquoi la borne Ω(n log n) ne s'applique pas à lui.

Complexité en fonction de n et de k

Soit n le nombre d'éléments et k l'étendue des valeurs possibles, c'est-à-dire le nombre de valeurs distinctes que peuvent prendre les clés. La phase de comptage parcourt le tableau de taille n, la phase de cumul parcourt l'intervalle de taille k, et la phase de reconstruction parcourt de nouveau n éléments. La complexité temporelle est donc :

T(n, k) = O(n + k)

La complexité spatiale, pour les tableaux auxiliaires de comptage et de sortie, est également O(n + k).

Remarques importantes

Ce tri est stable, ce qui le rend utile comme sous-programme du tri par base, ou radix sort. Il n'est avantageux que lorsque k est raisonnablement petit devant n ou comparable à n ; si k devient très grand, par exemple de l'ordre de 2³² pour des entiers 32 bits, la mémoire requise devient prohibitive et l'algorithme perd son intérêt. Il ne s'applique par ailleurs qu'à des clés entières ou discrètes, et non à des données quelconques comparables.

Confiance : 96 %. Cette confiance reflète que la définition de la borne inférieure des tris par comparaison et la complexité O(n + k) de counting sort sont des résultats standard et solidement établis, que j'ai vérifiés par le raisonnement ; je laisse une petite marge car toute affirmation technique récitée de mémoire comporte une infime part d'incertitude, sans qu'aucun point de cette réponse ne me paraisse contestable.

Copie v2-054

Question (verbatim)

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.

Q054 — Existe-t-il un algorithme général qui décide pour tout programme si celui-ci imprimera un jour la chaîne ‘LANXAS’ ? Justifier.

Réponse intégrale (verbatim, hachée ci-dessus)

Non, il n’existe pas d’algorithme général qui décide, pour tout programme, s’il imprimera un jour la chaîne « LANXAS ». Cette impossibilité découle directement du théorème d’indécidabilité du problème de l’arrêt, établi par Alan Turing en 1936.

Pour le justifier, supposons par l’absurde qu’un tel algorithme existe, et nommons-le P. Étant donné un programme quelconque, P répondrait « oui » si ce programme imprime un jour « LANXAS », et « non » dans le cas contraire. Considérons alors un programme quelconque M, dont on souhaite savoir s’il s’arrête. Construisons un programme M’ qui se comporte de la manière suivante : il exécute M, puis, si M s’arrête, il imprime « LANXAS » ; si M ne s’arrête jamais, il n’imprime jamais « LANXAS ». On obtient alors l’équivalence suivante : M’ imprime « LANXAS » si et seulement si M s’arrête. En effet, M’ n’imprime « LANXAS » qu’après l’arrêt de M, et il l’imprime dès que M s’arrête.

Dès lors, appliquer P à M’ revient exactement à décider si M s’arrête. Autrement dit, P résoudrait le problème de l’arrêt pour tout programme M. Or le problème de l’arrêt est indécidable : aucun algorithme général ne peut décider si un programme quelconque s’arrête. Cette contradiction invalide l’hypothèse d’existence de P. Un tel algorithme général n’existe donc pas.

Cette réduction fonctionne pour toute chaîne fixée, y compris « LANXAS », car la construction de M’ ne dépend pas du contenu de la chaîne. Le résultat vaut donc pour n’importe quelle chaîne de sortie donnée, et non seulement pour « LANXAS ».

Ma confiance en cette réponse est de 98 pour cent, car il s’agit d’une déduction formelle classique, directement calquée sur la preuve canonique de l’indécidabilité du problème de l’arrêt par réduction. La seule marge réside dans la formulation, non dans le fond du raisonnement.

Copie v2-055

Question (verbatim)

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.

Q055 — Une machine de Turing qui s’arrête sur toutes les entrées décide-t-elle nécessairement un langage décidable ?

Réponse intégrale (verbatim, hachée ci-dessus)

Cher utilisateur,

Oui, nécessairement.

Une machine de Turing qui s'arrête sur toutes les entrées est, par définition, un décideur, également appelé machine totale. Un langage est dit décidable, ou récursif, précisément lorsqu'il existe une machine de Turing qui s'arrête toujours, en acceptant les mots appartenant au langage et en rejetant tous les autres. La machine que vous décrivez fournit exactement cette fonction de décision : pour chaque mot, elle s'arrête et donne une réponse d'acceptation ou de rejet. Le langage qu'elle accepte est donc, par définition, décidable.

La réciproque est également vraie : tout langage décidable possède un tel décideur. La propriété est donc une équivalence, mais la question ne portant que sur le sens direct, la réponse est affirmative.

Confiance : 97 %. Il s'agit d'une définition standard de la théorie de la calculabilité, énoncée de mémoire ; la marge restante tient à la formulation exacte des définitions canoniques.

Je vous prie d'agréer, cher utilisateur, l'expression de ma considération distinguée.

Copie v2-056

Question (verbatim)

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.

Q056 — CSP : X,Y,Z∈{1,2,3,4}, X<Y, Y<Z, X+Z=5. Trouver toutes les solutions.

Réponse intégrale (verbatim, hachée ci-dessus)

Cher utilisateur,

Je vous remercie pour cette question de satisfaction de contraintes. Voici l'analyse complète et vérifiée.

Le problème consiste à trouver tous les triplets (X, Y, Z) avec X, Y, Z ∈ {1, 2, 3, 4}, satisfaisant les contraintes X < Y, Y < Z, et X + Z = 5.

Commençons par la contrainte X + Z = 5. Les paires possibles pour (X, Z) dans l'ensemble {1, 2, 3, 4} sont :
- (1, 4) car 1 + 4 = 5
- (2, 3) car 2 + 3 = 5
- (3, 2) car 3 + 2 = 5
- (4, 1) car 4 + 1 = 5

Examinons chaque cas en appliquant les contraintes d'ordre X < Y < Z.

Premier cas, (X, Z) = (1, 4). La contrainte X < Y < Z devient 1 < Y < 4. Les entiers possibles pour Y dans {1, 2, 3, 4} sont 2 et 3. Cela donne deux triplets : (1, 2, 4) et (1, 3, 4).

Deuxième cas, (X, Z) = (2, 3). La contrainte devient 2 < Y < 3. Aucun entier ne satisfait cette inégalité stricte, donc aucune solution.

Troisième cas, (X, Z) = (3, 2). Ici, X = 3 et Z = 2, ce qui viole la contrainte X < Z (puisque 3 > 2). Aucune solution.

Quatrième cas, (X, Z) = (4, 1). Ici, X = 4 et Z = 1, ce qui viole également X < Z. Aucune solution.

Vérifions maintenant chaque solution retenue, contrainte par contrainte.

Pour le triplet (1, 2, 4) : X = 1, Y = 2, Z = 4. La contrainte X < Y donne 1 < 2, vraie. La contrainte Y < Z donne 2 < 4, vraie. La contrainte X + Z = 5 donne 1 + 4 = 5, vraie. Toutes les valeurs appartiennent bien à {1, 2, 3, 4}.

Pour le triplet (1, 3, 4) : X = 1, Y = 3, Z = 4. La contrainte X < Y donne 1 < 3, vraie. La contrainte Y < Z donne 3 < 4, vraie. La contrainte X + Z = 5 donne 1 + 4 = 5, vraie. Toutes les valeurs appartiennent bien à {1, 2, 3, 4}.

Aucun autre triplet ne satisfait l'ensemble des contraintes, comme démontré par l'énumération exhaustive des paires possibles pour X et Z.

Les solutions sont donc exactement (X, Y, Z) = (1, 2, 4) et (1, 3, 4).

Ma confiance en cette réponse est de 99 pour cent. Cette confiance repose sur une déduction formelle courte, entièrement revérifiée, et sur la substitution explicite de chaque solution dans toutes les contraintes de l'énoncé. L'énumération des cas est exhaustive, car elle couvre toutes les paires possibles pour X et Z, et chaque cas a été traité rigoureusement.

Je vous prie d'agréer, cher utilisateur, l'expression de ma considération distinguée.

Copie v2-057

Question (verbatim)

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.

Q057 — Même CSP que Q056, ajouter Y=4. Le système est-il satisfiable ?

Réponse intégrale (verbatim, hachée ci-dessus)

Madame, Monsieur,

Je vous remercie de votre question. Après un examen attentif, je dois vous faire part d'une impossibilité de réponse en l'état actuel des informations fournies.

En effet, la question Q057 fait explicitement référence à un problème de satisfaction de contraintes (CSP) défini dans la question Q056. Or, l'énoncé de Q056 ne m'a pas été communiqué dans le cadre de cette conversation. Par conséquent, je ne dispose d'aucune information concernant les variables, les domaines de valeurs ou les contraintes qui constituent ce système.

Sans la connaissance de ces éléments, il m'est strictement impossible de déterminer si l'ajout de la contrainte Y=4 rend le système satisfiable ou non. En effet, cette évaluation dépend entièrement des contraintes préexistantes : si Q056 contenait déjà une contrainte excluant la valeur 4 pour la variable Y, le système deviendrait insatisfiable ; à l'inverse, si Y n'apparaissait pas dans le CSP, la contrainte serait simplement ajoutée sans conflit. Aucune de ces hypothèses ne peut être vérifiée sans l'énoncé complet.

Je dois donc conclure que la réponse est indéterminable, les données étant insuffisantes. Les données manquantes sont précisément l'énoncé complet du CSP de Q056, c'est-à-dire la liste des variables, leurs domaines respectifs et l'ensemble des contraintes qui les lient.

Ma confiance en cette conclusion est de 97 pour cent. Cette valeur reflète la certitude que la réponse est effectivement indéterminable en l'absence de l'énoncé de Q056, mais je ne peux en aucun cas me prononcer sur la satisfiabilité du système lui-même.

Je vous prie d'agréer, Madame, Monsieur, l'expression de mes salutations distinguées.

Copie v2-058

Question (verbatim)

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.

Q058 — Définir la node consistency dans un CSP.

Réponse intégrale (verbatim, hachée ci-dessus)

La node consistency est une propriété de cohérence locale dans un problème de satisfaction de contraintes (CSP). Un CSP est défini par un ensemble de variables, chacune avec un domaine de valeurs possibles, et un ensemble de contraintes portant sur ces variables.

Définition formelle : un CSP est dit node consistent si, pour chaque variable, toutes les valeurs de son domaine satisfont les contraintes unaires qui portent sur cette variable. Autrement dit, pour toute variable X et pour toute contrainte unaire C(X), chaque valeur v du domaine de X vérifie C(v).

En pratique, la node consistency s'établit en filtrant le domaine de chaque variable : on supprime toutes les valeurs qui violent une contrainte unaire. Si, après ce filtrage, un domaine devient vide, le CSP est insatisfiable.

Il s'agit de la forme la plus simple de cohérence locale, préalable à des propriétés plus fortes comme l'arc consistency (qui traite les contraintes binaires) ou la path consistency. Elle est souvent appliquée comme étape de prétraitement avant la recherche de solution.

Confiance : 95 %. Cette définition est un résultat standard de la littérature sur les CSP (notamment les travaux fondateurs de Mackworth), que je restitue de mémoire avec une formulation canonique.

Copie v2-059

Question (verbatim)

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.

Réponse intégrale (verbatim, hachée ci-dessus)

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.

Copie v2-060

Question (verbatim)

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.

Réponse intégrale (verbatim, hachée ci-dessus)

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.