Discussion :

[mido1951]

bonjour les amis,

Quelle est la différence entre un problème Np-Complet et un problème Np-Hard?
Comment savoir si un problème est Np-complet ou un problème Np-Hard?
est-ce que vous pouvez me donner un exemple de chaque type de problème?

Merci.

[usri06]

En réalité il y a deux types des problèmes : des problèmes de décision et les problèmes d'optimisation .

Pour les problèmes de décision , les algorithmes doivent répondre par oui ou par non par exemple (existe t 'il ... ?)

Alors que pour les problèmes d'optimisation , les algorithmes doivent répondre par des valeurs (comme la valeur de min & max ) , des chemins (comme le plus court chemin ) ,...

Le NP-complet concerne les problèmes de décision
Alors que le NP-difficile concerne les problèmes d'optimisation

[mido1951]

merci pour votre réponse cher ami