Liasse v2-041 à v2-050

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. Q041 — Comparer la complexité asymptotique de n^20 et 1.001^n lorsque n→∞.

**Réponse :** Lorsque $n \to \infty$, la fonction $1.001^n$ domine asymptotiquement la fonction $n^{20}$. En notations asymptotiques, on a $n^{20} = o(1.001^n)$. **Justification :** Pour comparer la croissance asymptotique de ces deux fonctions, on examine la limite du quotient $\lim_{n \to \infty} \frac{n^{20}}{1.001^n}$. Un résultat fondamental d'analyse stipule que pour toute base $a > 1$ et tout exposant réel $k > 0$, une fonction exponentielle de base $a$ croît strictement plus vite qu'une fonction polynomiale de degré $k$. Par conséquent, cette limite vaut $0$. On peut également le vérifier en comparant les logarithmes. $\ln(n^{20}) = 20 \ln n$ et $\ln(1.001^n) = n \ln 1.001$. La fonction linéaire $n \ln 1.001$ diverge vers $+\infty$ bien plus rapidement que la fonction logarithmique $20 \ln n$. Ainsi, $\ln(1.001^n) - \ln(n^{20})$ tend vers $+\infty$, ce qui implique que $\frac{1.001^n}{n^{20}}$ tend vers $+\infty$ et par inversion $\frac{n^{20}}{1.001^n}$ tend vers $0$. Il convient de préciser que cette domination asymptotique ne s'applique qu'à partir d'un seuil suffisamment grand de $n$. Pour des valeurs petites ou modérées, la puissance $n^{20}$ peut temporairement dépasser l'exponentielle. Cependant, la complexité asymptotique se définit par le comportement limite quand $n$ tend vers l'infini, auquel cas l'exponentielle l'emporte définitivement et s'éloigne indéfiniment de la puissance. **Confiance :** 100 %

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. Q042 — Si CLIQUE est résolu en temps polynomial, quelle conséquence standard en complexité ?

Réponse : P = NP. Justification : Le problème CLIQUE est un problème NP-complet. La définition formelle de la NP-complétude stipule qu'un problème est NP-complet s'il appartient à la classe NP et si tout autre problème de NP peut y être réduit en temps polynomial. Par conséquent, si un seul problème NP-complet admet un algorithme s'exécutant en temps polynomial, alors tous les problèmes de NP peuvent être résolus en temps polynomial en appliquant d'abord la réduction polynomiale, puis l'algorithme polynomial supposé. Cette chaîne de réductions implique directement l'égalité des classes P et NP. Cette implication est un résultat standard et fondamental de la théorie de la complexité computationnelle. Confiance : 100 %

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. Q043 — Un problème co-NP-complet est-il nécessairement NP-complet ? Répondre sans supposer P=NP.

**Réponse :** Non. **Justification :** Un problème est co-NP-complet s'il appartient à la classe co-NP et si tout problème de co-NP se réduit polynomialement à lui. Un problème est NP-complet s'il appartient à la classe NP et si tout problème de NP se réduit polynomialement à lui. Les classes NP et co-NP sont liées par la complémentarité : un langage L est dans co-NP si et seulement si son complémentaire L̄ est dans NP. Si un problème co-NP-complet était nécessairement NP-complet, il appartiendrait à NP. Cela entraînerait co-NP ⊆ NP. Par symétrie du complément, cela impliquerait également NP ⊆ co-NP, donc NP = co-NP. L'égalité NP = co-NP est un problème ouvert majeur en théorie de la complexité, largement conjecturé comme faux par la communauté scientifique. Si NP ≠ co-NP, les problèmes co-NP-complets ne font pas partie de NP et sont donc strictement hors de la NP-complétude. Sans supposer P = NP, ni même NP = co-NP, il n'existe aucune deduction logique qui impose cette appartenance. La prémisse selon laquelle un problème co-NP-complet serait nécessairement NP-complet est donc fausse dans le cadre standard de la complexité algorithmique. **Confiance :** 100 %

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. Q044 — Expliquer pourquoi un certificat polynomialement vérifiable ne signifie pas que le certificat est polynomialement trouvable.

Réponse : Un certificat polynomialement vérifiable ne garantit pas qu'il soit polynomialement trouvable car la validation rapide d'une solution proposée et la génération rapide de cette solution relèvent de complexités computationnelles fondamentalement différentes. L'existence d'un vérificateur efficace n'implique pas l'existence d'un algorithme de construction efficace. Justification : En théorie de la complexité, un problème décisionnel appartient à la classe NP si, pour toute instance positive, il existe un certificat dont la validité peut être vérifiée par un algorithme déterministe en temps polynomial par rapport à la taille de l'instance. Cette définition ne concerne que la phase de validation. La phase de recherche, en revanche, consiste à explorer un espace de candidats potentiellement exponentiel afin d'en extraire un qui satisfait le vérificateur. Même si chaque candidat peut être testé rapidement, l'absence de structure exploitable pour diriger la recherche impose, dans le pire des cas, un nombre exponentiel d'appels au vérificateur. Cette distinction est au cœur de la question ouverte P versus NP. Si tout certificat vérifiable en temps polynomial était effectivement trouvable en temps polynomial, alors chaque problème de NP admettrait un algorithme de résolution en temps polynomial, ce qui entraînerait l'égalité P = NP. À ce jour, aucune preuve ne démontre cette égalité, et la structure des réductions polynomiales montre que la vérification et la recherche sont des propriétés indépendantes. Vérification symbolique de l'exemple du voyageur de commerce : Pour une instance de taille n, un certificat est une permutation de sommets. Le vérificateur calcule la somme des poids des arêtes consécutives en O(n) opérations élémentaires, puis compare le résultat à une borne B en O(1). La complexité totale de la vérification est donc polynomiale, précisément O(n). En revanche, le nombre de permutations possibles est n!. Une recherche exhaustive nécessite jusqu'à n! appels au vérificateur, ce qui croît exponentiellement. Aucun algorithme connu ne réduit systématiquement n! à un polynôme de n sans hypothèse P = NP. La vérification reste rapide, mais la découverte du bon certificat impose une exploration exponentielle dans le modèle général. Par conséquent, la polynomialement vérifiable concerne la complexité de la validation d'une solution déjà fournie, tandis que la polynomialement trouvable concerne la complexité de la construction ou de l'extraction de cette solution à partir de l'instance seule. L'absence de mécanisme général de réduction de l'espace de recherche explique pourquoi la première propriété n'entraîne pas la seconde. Confiance : 100 %.

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. Q045 — Le problème de l’arrêt est-il NP-difficile ? Préciser pourquoi la question dépend de la notion de réduction employée.

Réponse : Oui, le problème de l’arrêt est NP-difficile au sens des réductions polynomiales à un seul passage, mais cette qualification dépend strictement de la classe de réduction retenue et des conventions définitionnelles employées. Justification : 1. Cadre formel et réduction polynomiale : Un problème B est dit NP-difficile si tout problème A appartenant à NP se réduit à B par une réduction polynomiale à un seul passage (notée A ≤_p B). Pour le problème de l’arrêt, on peut construire, à partir de n’importe quelle instance d’un problème NP-complet (par exemple SAT), une machine de Turing M et une entrée w telles que M s’arrête sur w si et seulement si l’instance initiale est une réponse positive. Cette transformation est calculable en temps proportionnel à la taille de l’entrée, donc en temps polynomial. Par conséquent, SAT ≤_p Arrêt, ce qui implique que le problème de l’arrêt est NP-difficile sous cette notion de réduction. 2. Dépendance vis-à-vis du type de réduction : La notion d’NP-difficulté n’est pas une propriété intrinsèque du problème mais une propriété relative à la classe de réduction utilisée. - Avec des réductions polynomiales ou logarithmiques à un seul passage, le problème de l’arrêt est bien NP-difficile, comme démontré ci-dessus. - Avec des réductions de Turing, le problème de l’arrêt est également NP-difficile, mais cette qualification perd de sa pertinence analytique car il devient complet pour des classes bien plus puissantes. Une oracle Arrêt permet de décider tout problème décidable, ce qui rend le problème de l’arrêt Turing-complet pour la classe des problèmes récursifs, et donc NP-difficile, PSPACE-difficile, EXP-difficile, etc. - Si l’on adopte une convention restrictiva qui réserve la notion d’NP-difficulté aux seuls problèmes décidables, ou qui exige que la réduction préserve la décidabilité de la cible, alors le problème de l’arrêt ne peut pas être qualifié d’NP-difficile. Dans ce cadre, la question devient mal posée car elle croise la théorie de la calculabilité (indécidabilité) et la théorie de la complexité classique (classes de problèmes décidables). 3. Synthèse sur la dépendance : La réponse varie donc selon que l’on considère des réductions à un seul passage (NP-difficile), des réductions de Turing (NP-difficile mais beaucoup plus difficile), ou des définitions canoniques qui excluent les problèmes indécidables du champ de la complexité. Sans préciser la classe de réduction et le cadre définitionnel, la qualification d’NP-difficile reste ambiguë. Confiance : 95 %

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. Q046 — Donner une réduction conceptuelle de 3-coloration vers un CSP fini.

**Réponse** On réduit le problème de 3-coloration à un CSP fini par un encodage direct : les sommets du graphe deviennent des variables, l'ensemble des trois couleurs constitue le domaine unique, et chaque arête se traduit par une contrainte binaire d'inégalité. **Justification** Soit G = (V, E) une instance de 3-coloration. On construit un CSP fini S = (X, D, C) selon la procédure suivante : 1. Variables : X = {x_v | v ∈ V}. Chaque variable x_v correspond à un sommet v du graphe. 2. Domaine : D = {0, 1, 2}. Chaque variable x_v prend sa valeur dans D. Le domaine est fini et de taille constante. 3. Contraintes : Pour chaque arête {u, v} ∈ E, on introduit une contrainte binaire C_{u,v} portée par le couple de variables (x_u, x_v). Cette contrainte est définie comme la relation R_{u,v} ⊆ D² telle que R_{u,v} = {(a, b) ∈ D² | a ≠ b}. L'ensemble des contraintes est C = {C_{u,v} | {u, v} ∈ E}. Le CSP obtenu est fini car D est de cardinal constant et C est un ensemble fini de relations finies. Une affectation satisfaisante pour (X, D, C) correspond bijectivement à un coloriage valide de G en trois couleurs : si deux sommets adjacents reçoivent la même couleur, la contrainte C_{u,v} est violée ; réciproquement, toute affectation respectant les contraintes C_{u,v} pour toutes les arêtes définit un coloriage propre. La réduction est calculable en temps linéaire par rapport à |V| + |E| et préserve la structure décisionnelle du problème. Aucune prémisse fausse, aucune information insuffisante ni cas indéterminable n'intervient dans cet encodage standard. **Confiance** 100 %

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. Q047 — Une table de hachage avec adressage ouvert peut-elle avoir un facteur de charge supérieur à 1 ?

Réponse : Non. Justification : Dans une table de hachage à adressage ouvert, chaque case du tableau principal peut contenir au plus un élément. Le facteur de charge α est défini par le rapport α = n / m, où n représente le nombre d'éléments effectivement stockés et m la capacité totale du tableau. Puisque chaque insertion occupe une case distincte et qu'il n'existe pas de structure externe permettant de regrouper plusieurs valeurs dans un même emplacement, le nombre d'éléments ne peut jamais dépasser le nombre de cases disponibles. On a donc systématiquement n ≤ m, ce qui impose mathématiquement α ≤ 1. Un facteur de charge strictement supérieur à 1 est impossible dans cette configuration. Lorsque le tableau atteint la saturation (α = 1), toute tentative d'insertion supplémentaire échoue ou déclenche obligatoirement un redimensionnement pour augmenter m. Cette limitation propre à l'adressage ouvert ne doit pas être confondue avec celle des tables de hachage à adressage fermé par listes chaînées, où le facteur de charge peut effectivement excéder 1 car plusieurs éléments peuvent être indexés par une même position de hachage. Confiance : 100 %

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. Q048 — Dans un arbre AVL, quelle est la complexité pire cas de recherche, insertion et suppression ?

**Réponse :** O(log n) pour la recherche, l'insertion et la suppression. **Justification :** Un arbre AVL est une structure de recherche binaire autoéquilibrante qui impose que la différence de hauteur entre les sous arbres gauche et droit de chaque nœud soit en valeur absolue inférieure ou égale à 1. Cette contrainte garantit que la hauteur h de l'arbre reste strictement bornée par 1,44 log₂(n + 2), ce qui implique h ∈ O(log n). - **Recherche :** Elle consiste à suivre un chemin unique de la racine vers une feuille en comparant les clés. Le nombre maximum de comparaisons est égal à la hauteur, donc Θ(log n) dans le pire cas. - **Insertion :** Elle comporte une phase descendante de parcours en O(log n) pour trouver la position, l'ajout d'un nœuf feuille, puis une remontée le long du chemin de insertion pour recalculer les facteurs d'équilibre. Si un déséquilibre est détecté, des rotations locales (simple ou double) sont exécutées. Chaque rotation s'exécute en temps constant, et le nombre maximal de rotations sur un chemin est borné par O(log n) (généralement au plus deux rotations, donc O(1), mais le parcours domine). La complexité totale reste Θ(log n). - **Suppression :** Elle nécessite un parcours descendant en O(log n) pour localiser le nœud, un retrait éventuel, puis une remontée pour restaurer l'équilibre. Comme pour l'insertion, les rotations sont locales et constantes, mais le parcours initial et la propagation des corrections le long du chemin restent bornés par la hauteur, d'où une complexité pire cas de Θ(log n). Aucune prémisse fausse ni information insuffisante ne rend la question indéterminable. La borne O(log n) est classique, rigoureusement démontrée, et vérifiable par induction sur la hauteur minimale des arbres AVL de n nœuds. **Confiance :** 100 %

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. Q049 — Une file de priorité binaire permet-elle de trouver le minimum en O(1) et de le supprimer en O(log n) ?

Réponse : Oui. Justification : Une file de priorité implémentée par un tas binaire conserve systématiquement son élément minimal à la racine. La consultation de ce minimum correspond à un simple accès au premier noeud de la structure, ce qui s'exécute en temps constant O(1). La suppression du minimum nécessite de remplacer la racine par le dernier élément du tas, de décrémenter la taille, puis de restaurer la propriété de tas par un processus de descente vers le bas. La hauteur d'un tas binaire à n éléments est strictement inférieure à log2(n) + 1, ce qui borne le nombre maximal d'échanges ou de comparaisons nécessaires à la réorganisation. La complexité totale de l'opération de suppression est donc bien O(log n). Confiance : 100 %.

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. Q050 — Quelle est la complexité amortie de append dans un tableau dynamique à redimensionnement géométrique ?

**Réponse :** La complexité amortie de `append` est O(1). **Justification :** Dans un tableau dynamique à redimensionnement géométrique, la capacité est multipliée par un facteur constant strictement supérieur à 1 (classiquement 2) dès que le tableau est saturé. L'ajout d'un élément occupe un temps constant en temps normal. Lorsqu'un redimensionnement est déclenché, une nouvelle zone mémoire de taille doublée est allouée, l'ensemble des `n` éléments existants y est copié, puis le nouvel élément est inséré. Ce coût de copie est en O(n), mais il ne se produit qu'après exactement `n` insertions consécutives. En analysant le coût total de `m` opérations `append`, on constate que chaque élément est copié au plus une fois par redimensionnement, et le nombre de redimensionnements est logarithmique en `m`. Le coût cumulé des copies sur `m` opérations est borné par une série géométrique convergente : `m + m/2 + m/4 + ... ≤ 2m`. Ainsi, le coût total reste proportionnel à `m`, ce qui donne un coût moyen par opération égal à `O(m)/m = O(1)`. Cette analyse amortie suppose explicitement que le facteur de croissance géométrique est constant et strictement supérieur à 1, ce qui est le cas par définition du redimensionnement géométrique standard. **Confiance :** 100 %