En pratique si. Pour cela on part d'un problème NP-Complet de référence, le problème SAT (cf Problème_SAT).
Pour montrer que P=NP en générale (c'est ce qui est fait dans le papier du journal) on prends un problème, on montre que si il peut être résolu de manière polynomial alors SAT peut l'être (et donc par transitivité tous les autres problèmes NP). Ensuite on propose un algorithme de la classe P pour notre problème. Ce qui nous donne directement un algorithme de la classe P pour SAT.
Maintenant prenons un autre problème NP. On peut le résoudre (par définitions de NP) par une machine de Turing non déterministe (c'est long à traduire, c'est chiant, mais ce n'est pas compliqué, d'ailleurs il doit exister un compilateur C vers machine de turing non déterministe). En très gros écrire un algorithme non déterministe c'est écrire un algorithme qui vérifie une solution (cf mon post précédent).
Mais la preuve de la NP-complétude de SAT nous donne l'algorithme pour transformer le code polynomiale exécuté par la machine de Turing non déterministe en un problème SAT de même classe de complexité, et comme on sait résoudre SAT de manière polynomiale (sous réserve que P=NP) alors on a l'algo de la classe P.
Donc pour ceux qui n'ont pas compris mes explication pas très claire, écrire un traducteur qui part d'un algo non déterministe (un algo qui vérifie la solution) et qui nous donne un code polynomiale est « simple ». En faire un qui propose un algo efficace — autre que des O(N25689) — est une autre paire de manche, mais si le théorème s'avère vrai, ce compilateur devrait apparaître rapidement.
[^] # Re: Des commentaires de chercheur ?
Posté par Diagonale de Cantor (site web personnel) . En réponse au journal P=NP démontré ?. Évalué à 7.
En pratique si. Pour cela on part d'un problème NP-Complet de référence, le problème SAT (cf Problème_SAT).
Pour montrer que P=NP en générale (c'est ce qui est fait dans le papier du journal) on prends un problème, on montre que si il peut être résolu de manière polynomial alors SAT peut l'être (et donc par transitivité tous les autres problèmes NP). Ensuite on propose un algorithme de la classe P pour notre problème. Ce qui nous donne directement un algorithme de la classe P pour SAT.
Maintenant prenons un autre problème NP. On peut le résoudre (par définitions de NP) par une machine de Turing non déterministe (c'est long à traduire, c'est chiant, mais ce n'est pas compliqué, d'ailleurs il doit exister un compilateur C vers machine de turing non déterministe). En très gros écrire un algorithme non déterministe c'est écrire un algorithme qui vérifie une solution (cf mon post précédent).
Mais la preuve de la NP-complétude de SAT nous donne l'algorithme pour transformer le code polynomiale exécuté par la machine de Turing non déterministe en un problème SAT de même classe de complexité, et comme on sait résoudre SAT de manière polynomiale (sous réserve que P=NP) alors on a l'algo de la classe P.
Donc pour ceux qui n'ont pas compris mes explication pas très claire, écrire un traducteur qui part d'un algo non déterministe (un algo qui vérifie la solution) et qui nous donne un code polynomiale est « simple ». En faire un qui propose un algo efficace — autre que des O(N25689) — est une autre paire de manche, mais si le théorème s'avère vrai, ce compilateur devrait apparaître rapidement.