Science : Science de Normand

Je viens de lire un article tout à fait fascinant dans "Pour la science" de ce mois. Il concerne la fameuse conjecture "P=NP". L'auteur de l'article, Jean-Paul Delahaye (familier des vieux lecteurs de Science et Vie junior comme moi!), nous explique qu'une façon de démontrer cette conjecture serait de démontrer qu'elle est en fait indécidable ( c'est-à-dire qu'on ne peut démontrer dans le système d'axiome considéré qu'elle est vraie ou fausse). Cela ressemble à un syllogisme ! Il cite un exemple très précis en arithmétique - considérons la conjecture suivante, dite conjecture de Goldbach : "Tout nombre pair supérieur à 4 est somme de deux nombres premiers". Si cette proposition est indécidable, on ne peut démontrer qu'elle est fausse. Or, une façon très simple de démontrer qu'elle est fausse serait de trouver un contre-exemple. Donc, si la conjecture est indécidable, cela signifie qu'on ne peut trouver de contre-exemple, donc qu'elle est vraie ! Du coup, la proposition serait-elle en fait décidable ? Je ne le pense pas : l'indécidabilité dans le sens "vrai" signifie à mon avis qu'on ne pourrait vérifier le résultat qu'en énumérant tous les cas - autrement dit qu'il n'y aurait pas de raisons "profondes" dans le système d'axiome considéré permettant de l'établir. Cette énumération est évidemment impossible car le nombre de cas est infini, d'où l'indécidabilité. Je crois d'ailleurs que lorsque le nombre de cas est fini (ou pas trop grand !), les informaticiens n'hésitent pas à énumérer tous les cas pour "démontrer" certains énoncés.

Ce mode de raisonnement basé sur l'indécidabilité pourrait donc peut-être s'appliquer à tout résultat très général portant sur des ensembles infinis, pouvant être réfuté simplement par un contre-exemple. Ainsi, si la conjecture de Riemann est indécidable, elle est vraie, car on ne peut alors trouver de contre-exemple, et de même peut-être pour la conjecture "P=NP" !