Quelqu'un peut-il s'il vous plaît donner un exemple d'exemple?Si un problème est dans NP, il n'y a pas d'algorithme de temps polynomial connu pour le résoudre

Question

Y a-t-il un algorithme de temps polynomial connu pour résoudre un problème que ce problème est dans NP.On m'a dit que c'est faux mais je ne peux penser à aucun exemple de contre-exemple maintenant.

Answer 1

np est la classe des problèmes de décision où toute instance avec une réponse "oui" a une preuve que la réponse est oui qui peut être vérifiée en temps polynomial.NP contient tous les problèmes résolvables en temps polynomial.Par conséquent, il y a beaucoup de problèmes dans NP avec des algorithmes de temps polynomial connus.

Si vous parlez de problèmes de NP-Complets, c'est une question totale.Il y a (à ce moment-là) Aucun problème NP-complet avec un algorithme de temps polynomial connu pour le résoudre.

Quelqu'un peut trouver une preuve que, pour un problème complet de NP, il n'y a pas de problème complet NP avec un algorithme de temps polynomial pour le résoudre - pas seulement aucun algorithme connu, mais pas d'algoritme du tout.

D'autre part, une personne peut réellement trouver une NP-complète pouvant être résolue en temps polynomial.C'est peu probable cependant.