Intuitivement, ce n'est pas une preuve, le fait qu'on n'ait pas de réduction pour ces problèmes signifierait qu'ils dont moins dur que NP-complets : on arrive pas à exprimer SAT (NP complet) par exemple sous la forme de factorisation de nombre premiers ...
Donc à priori si on arrive à faire l'inverse, exprimer la factorisation sous la forme de SAT ou autre, on devrait prouver rigoureusement, si c'est pas déja fait, qu'ils sont plus faciles, et obtenir du même coup un algo polynomial, donc comme ça c'est pas très génant, en y réfléchissant un peu finalement.
[^] # Re: Il dit qu'il est pas d'accord.
Posté par thoasm . En réponse au journal P != NP : la preuve. Évalué à 2.
Donc à priori si on arrive à faire l'inverse, exprimer la factorisation sous la forme de SAT ou autre, on devrait prouver rigoureusement, si c'est pas déja fait, qu'ils sont plus faciles, et obtenir du même coup un algo polynomial, donc comme ça c'est pas très génant, en y réfléchissant un peu finalement.