Bonjour,
Je suis en train de réfléchir un peu à la conjecture P=NP et je me suis demandé si elle ne pourrait pas être indécidable dans le sens suivant. Il se pourrait que l'on ait un algorithme qui fonctionne effectivement en temps polynomial, mais que la preuve de ce fait soit indécidable, car elle pourrait découler par exemple d'une question dont on sait quelle indécidable. Pensez-vous que cela soit possible ?
on peut aussi se poser la question,quel est le plus grand entier naturel; un entier premier ou un entier composé ?on a donc pas besoin d'un algorithme.Envoyé par Sylvestre
aux deux réponses il y a une contradiction.
P = premier
NP = composé
P n'est pas égal à NP,
si P est vrai je multiplie par 2 et c'est faux
si NP est vrai je rajoute 1 et c'est faux
est ce indécidable?
Non, on ne peut pas se poser raisonnablement cette question.on peut aussi se poser la question,quel est le plus grand entier naturel; un entier premier ou un entier composé ?
Soit je ne comprends pas ta réponse, soit il y a un malentendu. Lorsque je parle de la conjecture P=NP, je veux parler du problème d'informatique théorique concernant la résolution des problèmes de décision. On peut avoir un énoncé du problème ici.
bonjour Erik
dommage
Bonjour,
Il me semble que c'est le sort de toute conjecture que de pouvoir être soit vraie, soit fausse, soit indécidable. Ce fut le cas pour le postulat d'Euclide ou pour l'axiome du choix...
Si je ne me trompe pas, indécidable, cela signifie que l'on peut construire deux modèles consistants dont l'un postulerait NP=P et l'autre NP#P. Cela n'implique pas nécessairement que l'on puisse relier NP=P à un autre "axiome" connu (type hypothèse du continu, AC,...)
On aurait alors des théorèmes vrais avec NP=P et d'autres vrais avec NP#P
Je pense que n'auras pas de difficulté à encaisser 1 M$ lorsque tu auras démontré que c'est indécidable
je n'en suis pas sûr, mais il me semble que Zinia confond les notions de proposition indécidable, et axiome indépendant (d'autres axiomes). Le postulat des parallèles est indépendants des autres axiomes d'Euclide, alors que la proposition de Gödel est indécidable (mais vraie, donc on ne peut pas ajouter sa négation comme axiome sans créer de contradiction).
Mais tout ça c'est des vieux souvenirs de la lecture de Smullyan, quelqu'un de mieux au courant peut-il commenter?
Moi non plus je ne suis pas sur mais wikipédia semble faire la même interprétation que moi :
http://fr.wikipedia.org/wiki/Ind%C3%A9cidabilit%C3%A9
Je m'associe à Ambrosio pour solliciter un avis autorisé
Je ne prétendrais pas que mon avis est autorisé, mais tu fais une grosse confusion, si l'on était capable de démontrer que la négation d'une proposition est contradictoire avec un ensemble d'axiomes alors la dite proposition ne serait pas indécidable, mais parfaitement démontrée (en tout cas dans le cadre d'une logique admettant le tiers exclu, la logique classique par exemple).
Le postulat des parallèles d'Euclide est indécidable à partir des autres axiomes de la géométrie ; l'axiome du Choix est indécidable dans la théorie ZF ; la commutativité est indécidable dans la théorie des groupes, etc.
Tu soulèves une autre question : une proposition peut-elle être vraie et indécidable ? Oui, si l'on fait la confusion entre théorie et modèle de cette théorie, par exemple, muni de l'addition est bien commutatif, mais je ne peux le démontrer sans ajouter quelque chose à la théorie des groupes...
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
Je suis tout à fait d'accord avec Mediat. Ma question originale a beaucoup à voir avec cela. J'aimerais bien réussir à comprendre s'il est possible qu'un algorithme se termine en temps polynomiale pour tous les inputs possibles, mais que ceci soit non démontrable. Je commence à avoir des doutes à ce sujet, mais je n'arrive pas à les préciser plus.
vous avez raison, c'est moi qui confonds tout.
Il me semble cependant que si un des problèmes NP complet tombe, tous tombent... Donc c'est démontrable.
Justement, ce que je veux dire c'est qu'il est peut-être possible que P=NP et que l'on ait un algorithme polynomial pour résoudre tous les problèmes NP, mais que le fait que l'algorithme est polynomial soit non démontrable. Dans ce cas, je ne suis pas sûr que l'on puisse dire une problème NP-complet est "tombé".
Prouver qu'un algorithme est polynomial est-il vraiment compliqué ?
J'ai réfléchi: je pense que tu es sur la bonne voie. 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.
Cependant, tu peux trouver un algo particulier et montrer qu'il est polynomial dans tous les cas.
C'est en gros le même problème que l'arrêt d'un programme
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 ?
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 ?
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.
C'est juste, mais je ne tiens pas vraiment à prouver la conjecture. Je veux seulement mettre une possibilité en évidence.Dans cette hypothèse la caractérisation de l'algo en question est indécidable mais cela n'induit rien sur NP=P
La suite de syracuse...
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
Bonjour,
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é
Peut-être voulais-tu dire "conjecture non résolue" (c'est un pléonasme) ?
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
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 !
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
Bonjour,
Soit un fichier A qui résout un problème NP Complet.
Soit un fichier B qui vérifie la solution.
Si le poids du fichier A est plus petit que le poids du fichier B, peut-on pour autant conclure que A s’exécute en temps NP ?
Un oubli, Merci.
