Bonjour,
Étant bien sûr allé glaner un peu ce qu'on trouve sur le web (Wikipédia par exemple) à propos de ma question, je reste néanmoins sur ma faim et c'est ce qui motive ce message.
Je veux au préalable insister sur le fait que je me place au conditionnel, je cherche à savoir la plausibilité historique de la chose et non sa véracité (je veux rester rigoureux mais je travaille dans la fiction, voir L'île logique).
Donc voici la question, j'essaye de préciser ensuite :
"Est-il concevable que dans la première moitié du 20e siècle on se soit déjà approché de la question P=?NP ?"
Je lis en effet que cette notion (NP-complétude) a été soulevée dans les années 70 isolément par messieurs Leven et Cook et je suppose que la présence physique des ordinateurs a dû les inspirer.
Pourtant D. Hilbert a parlé d'une sorte d'automatisation des preuves des maths, pensant peut-être qu'un jour on aurait "fini et démontré" les maths (je pense aussi à son 10e problème et à son 24e qu'il n'a finalement pas publié, à ses théories de la démonstration et à son questionnement sur les problèmes de décision) avant que K.Gödel ne vienne mettre à bas certains de ses espoirs avec son théorème d'incomplétude (1931) et je pense surtout à Turing et ses machines : forcément que, même avec sa machine universelle, il pouvait compter les étapes de déplacement de son curseur et donc avoir une idée de la complexité algorithmique des choses (par exemple le problème du voyageur de commerce, NP-complet, tel chemin est-il le plus court ?).
Je reformule ma question : Peut-on imaginer, envisager, qu'il puisse y avoir eu un mathématicien, logicien, pré-informaticien, qui ait soulevé la question P=?NP dans les années 30 par exemple ? Ou bien c'est impossible ? (car par exemple il manquait un théorème)
Et bien sûr, si cette personne aurait alors pu soulever le problème P=?NP on ne peut pas exclure qu'il l'ait résolu positivement en trouvant une formule ad'hoc.
Est-ce plausible d’imaginer un mathématicien tartampion qui aurait soulevé cela à l'époque ?
En clair, pour tâcher d'être plus rigoureux : les connaissances qu'on avait dans les années 20 ou 30 (sans les ordis !) étaient-elles suffisantes pour que puissent tout de même émerger les questions de complexité algorithmique et en particulier celle de P=?NP ?
En espérant avoir été clair ?
Merci à vous,
Cordialement,
Cédric
xxx déjà en place dans votre profil xxx
-----