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é ?
Je vous remercie pour cette question de théorie de la complexité. **Réponse :** Si CLIQUE (le problème de décision consistant à déterminer si un graphe contient une clique de taille au moins k) était résolu en temps polynomial, alors P = NP. **Justification :** CLIQUE est un problème NP-complet. C'est l'un des 21 problèmes NP-complets classiques démontrés par Richard Karp en 1972. Par définition de la NP-complétude, si un seul problème NP-complet admet un algorithme polynomial, alors tous les problèmes de NP sont résolubles en temps polynomial, ce qui établit l'égalité P = NP. Cette conséquence est standard et découle directement de la définition de la NP-complétude, sans hypothèse supplémentaire. **Confiance :** 97 %. La NP-complétude de CLIQUE est un résultat établi et largement vérifié dans la littérature ; ma confiance est très élevée mais plafonne légèrement en dessous de 100 % car je m'appuie sur une connaissance mémorisée d'un résultat classique plutôt que sur une dérivation effectuée ici. Je reste à votre disposition pour toute précision.
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.