Algorithmes qui fonctionnent en temps polynomial si p= np

Question

sur Wikipedia , il dit qu'il y a des algorithmes qui fonctionnaienten temps polynomial si et seulement si p= np.Ils ont donné un exemple (sans citation), mais y a-t-il d'autres?J'ai essayé de les regarder et je ne pouvais trouver aucun.

Answer 1

Wikipedia décrit l'algorithme universel de Levin.Ceci est un algorithme de problèmes vérifiables, ce qui est compétitif avec l'algorithme optimal (en quelque sorte).En particulier, la même approche serait exacte pour le problème tout problème dans NP, pas seulement la somme sous-ensembles.