Discussion :

[hnouna2007]

Bonjour,

Ma question est dans l'objet, puisse quelqu'un me parler de la complexité exponentielle de l'opération de projection dans les graphes conceptuels.

Cette complexité est calculée par rapport au nombre de nœuds du graphe à projeter ou du graphe sur lequel on fait la projection?

merci

[Ravaka]

Salut !

Si je me souviens bien de mes cours de Recherche Opérationnelle, NP ne signifie pas Non Polynomial. NP signifie Non déterministe et Polynomial.

NP-Complet veut dire que si t'as un algorithme polynomial qui résout un problème NP-Complet, tu peux résoudre les autres aussi en temps polynomial après une transformation du problème que tu veux résoudre.

Cette page peut aider : Théorie de la complexité des algorithmes

Après, je peux pas trop aider