Un problème difficile pour les PN est un problème oui/non où il est au moins aussi difficile de lui trouver une solution que de trouver une solution au problème le plus difficile dont la solution peut être rapidement vérifiée comme étant vraie. Certains problèmes NP difficiles sont ceux dont la solution peut être rapidement vérifiée (problèmes NP) et d'autres non. Les problèmes difficiles qui sont également des problèmes NP entrent dans une catégorie appelée NP-complet.
Un exemple de problème au moins aussi difficile à résoudre que tout autre problème dont nous pouvons rapidement vérifier les solutions, qui est également rapidement vérifiable (il est à la fois NP-dur et NP) :
Un vendeur ambulant veut visiter 100 villes en voiture, en commençant et en terminant son voyage à la maison. Il dispose d'une réserve d'essence limitée, de sorte qu'il ne peut parcourir qu'un total de 10 000 kilomètres. Il veut savoir s'il peut visiter toutes les villes sans manquer d'essence.
Les gens ne savent pas comment résoudre ce problème plus rapidement qu'en testant toutes les réponses possibles, mais si une solution est trouvée qui permet au vendeur de le faire, nous pouvons utiliser un algorithme pour vérifier qu'elle est vraie. Ce problème est également connu sous le nom de problème du vendeur itinérant.
Un exemple de problème qui est au moins aussi difficile à résoudre que tout autre problème dont nous pouvons rapidement vérifier les solutions, mais qui ne peut être vérifié rapidement (il est NP-dur, mais il n'est pas NP) :
si quelqu'un lance un programme qui va simplement,
et ne l'arrête jamais, est-ce qu'il va courir pour toujours ?
Il n'existe pas de moyen connu de trouver une solution à tous les problèmes de ce type, et cela non plus ne peut être vérifié.
Questions et réponses
Q : Qu'est-ce qu'un problème NP-hard ?
R : Un problème NP-difficile est un type de problème mathématique utilisé en informatique. Il s'agit d'un problème oui/non dont la solution est au moins aussi difficile à trouver que celle du problème le plus difficile dont la solution peut être rapidement vérifiée comme étant vraie.
Q : Une solution fonctionnelle peut-elle être vérifiée rapidement pour tous les problèmes NP-difficiles ?
R : Non, seuls certains problèmes NP-difficiles, appelés problèmes NP, ont des solutions qui peuvent être vérifiées rapidement.
Q : Comment s'appelle la catégorie des problèmes NP-difficiles qui sont aussi des problèmes NP ?
R : Les problèmes NP-durs qui sont aussi des problèmes NP entrent dans une catégorie appelée NP-complet.
Q : Tous les problèmes NP-difficiles sont-ils NP-complets ?
R : Non, tous les problèmes NP-difficiles ne sont pas NP-complets. Seuls ceux qui sont également des problèmes NP entrent dans cette catégorie.
Q : Les problèmes NP-difficiles sont-ils faciles à résoudre ?
R : Non, les problèmes NP-difficiles ne sont pas faciles à résoudre. En fait, il est au moins aussi difficile de trouver une solution à ces problèmes que de trouver une solution au problème le plus difficile dont la solution peut être rapidement vérifiée comme étant vraie.
Q : La résolution de problèmes NP difficiles présente-t-elle des avantages ?
R : Oui, la résolution de problèmes NP-difficiles peut présenter des avantages dans divers domaines, tels que l'informatique, la physique et les sciences sociales, car ils peuvent nécessiter des calculs et des modélisations complexes.
Q : Des recherches sont-elles en cours pour résoudre les problèmes NP-difficiles ?
R : Oui, la recherche sur la résolution des problèmes NP-difficiles se poursuit, car ces problèmes restent pertinents dans divers domaines et la découverte d'algorithmes et de solutions efficaces peut avoir des conséquences importantes.
