Réflexion sur P=NP

[Sylvestre]

Effectivement, on ne peut pas démontrer qu'un algo est polynomial à partir de toutes les entrées car on ne sait pas ce que fait le programme: il nous manque des hypothèses que l'on ne pourra pas donner.

Est-ce qu'il ne serait pas possible que l'on ne sache pas dire si un algorithme est polynomial même en voyant son code ? Cela ne me semble pas impossible, car je sais que G. Chaitin a exhibé un polynome en beaucoup de variables dépendant d'un paramètre n tel que la question qui est de savoir si pour tout n, le polynôme a un nombre fini de solutions n'est pas résoluble par algorithme. Dans mon cas, le polynôme représente mon algorithme hypothétique dont on a le code complet, mais dont il est impossible de dire s'il s'arrête en temps polynomial. Cela ne serait pas possible ?

[zinia]

Dans mon cas, le polynôme représente mon algorithme hypothétique dont on a le code complet, mais dont il est impossible de dire s'il s'arrête en temps polynomial. Cela ne serait pas possible ?

Bonjour,
J'ai du mal à imaginer un algorithme dont on ait le code explicite et dont on ne puisse dire s'il est polynomial ou non mais admettons.
Dans cette hypothèse la caractérisation de l'algo en question est indécidable mais cela n'induit rien sur NP=P. On se retrouve dans la même situation que lorsque djar exhibe un algorithme exponentiel ; le problème reste ouvert mais pas encore indécidable.
Il faudrait démontrer que tout algo résolvant tel pb NP complet s'exécute en un temps indécidable ?

[Sylvestre]

Bonjour,
J'ai du mal à imaginer un algorithme dont on ait le code explicite et dont on ne puisse dire s'il est polynomial ou non mais admettons.

Comme il existe des programmes très court (en nombre de lignes) dont on n'arrive pas à dire s'ils s'arrêtent, j'ai bien l'impression que l'on pourrait construire un programme court (en nombre de lignes) qui s'arrête en temps polynomial "indécidablement".

Je raconte peut-être des bêtises, mais j'espère bien que ma compréhension va s'améliorer au fil de cette discussion.

Dans cette hypothèse la caractérisation de l'algo en question est indécidable mais cela n'induit rien sur NP=P

C'est juste, mais je ne tiens pas vraiment à prouver la conjecture. Je veux seulement mettre une possibilité en évidence.

[sarsky]

Bonjour,
J'ai du mal à imaginer un algorithme dont on ait le code explicite et dont on ne puisse dire s'il est polynomial ou non mais admettons.

La suite de syracuse...

[acx01b]

bonjour, moi l'idée me plait bien

on peut inverser le problème de syracuse :
peut-on trouver un théorème (d'algèbre par exemple) qui soit indécidable, et construire un algorithme qui sera polynomial seulement si le théorème est vrai

[Médiat]

Bonjour,

peut-on trouver un théorème (d'algèbre par exemple) qui soit indécidable, et construire un algorithme qui sera polynomial seulement si le théorème est vrai

Je ne comprends pas bien cette phrase :
1) "théorème indécidable" est un oxymore
2) un énoncé n'est pas intrinsèquement indécidable, c'est toujours "dans une théorie" que la question peut se poser
3) que veut dire "vrai" ici ?

Exemple (désolé, j'emploie toujours le même, mais il est simple et efficace) : Dans la théorie des groupes (c'est bien de l'algèbre), l'énoncé est indécidable, que veut dire qu'il est vrai ou qu'il est faux ?

Peut-être voulais-tu dire "conjecture non résolue" (c'est un pléonasme) ?

[jobherzt]

On a des exemples qui ressemblent un peu à ca, parce exemple l'algorithme (probabiliste) de test de primalité de Miller-Rabin "deviendrait" deterministe et polynomial si on parvenait a prouver l'hypothese de Riemann.

Sachant par ailleurs que le fait qu'il existe un algorithme polynomial pour tester la primalité d'un nombre est un resultat assez recent !

[exciton]

Voici un algorithme polynomial si P=NP. Sa complexité est indécidable avec les techniques actuelles.

http://en.wikipedia.org/wiki/P_versu...ime_algorithms