Répondre à la discussion
Affichage des résultats 1 à 25 sur 25

Réflexion sur P=NP



  1. #1
    Sylvestre

    Réflexion sur P=NP


    ------

    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 ?

    -----

  2. Publicité
  3. #2
    leg

    Re : Réflexion sur P=NP

    Citation Envoyé par Sylvestre Voir le message
    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.
    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?

  4. #3
    erik

    Re : Réflexion sur P=NP

    on peut aussi se poser la question,quel est le plus grand entier naturel; un entier premier ou un entier composé ?
    Non, on ne peut pas se poser raisonnablement cette question.

  5. #4
    Sylvestre

    Re : Réflexion sur P=NP

    Citation Envoyé par leg Voir le message
    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.

  6. A voir en vidéo sur Futura
  7. #5
    leg

    Re : Réflexion sur P=NP

    Citation Envoyé par erik Voir le message
    Non, on ne peut pas se poser raisonnablement cette question.
    bonjour Erik
    dommage

  8. #6
    zinia

    Re : Réflexion sur P=NP

    Citation Envoyé par Sylvestre Voir le message
    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 ?
    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

  9. Publicité
  10. #7
    invite986312212
    Invité

    Re : Réflexion sur P=NP

    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?

  11. #8
    zinia

    Re : Réflexion sur P=NP

    Citation Envoyé par ambrosio Voir le message
    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).
    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é

  12. #9
    Médiat

    Re : Réflexion sur P=NP

    Citation Envoyé par ambrosio Voir le message
    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).
    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

  13. #10
    Sylvestre

    Re : Réflexion sur P=NP

    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.

  14. #11
    invite986312212
    Invité

    Re : Réflexion sur P=NP

    vous avez raison, c'est moi qui confonds tout.

  15. #12
    djar

    Re : Réflexion sur P=NP

    Il me semble cependant que si un des problèmes NP complet tombe, tous tombent... Donc c'est démontrable.

  16. Publicité
  17. #13
    Sylvestre

    Re : Réflexion sur P=NP

    Citation Envoyé par djar Voir le message
    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é".

  18. #14
    djar

    Re : Réflexion sur P=NP

    Prouver qu'un algorithme est polynomial est-il vraiment compliqué ?

  19. #15
    djar

    Re : Réflexion sur P=NP

    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

  20. #16
    Sylvestre

    Re : Réflexion sur P=NP

    Citation Envoyé par djar Voir le message
    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 ?

  21. #17
    zinia

    Re : Réflexion sur P=NP

    Citation Envoyé par Sylvestre Voir le message
    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 ?

  22. #18
    Sylvestre

    Re : Réflexion sur P=NP

    Citation Envoyé par zinia Voir le message
    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.

  23. Publicité
  24. #19
    sarsky

    Re : Réflexion sur P=NP

    Citation Envoyé par zinia Voir le message
    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...

  25. #20
    acx01b

    Re : Réflexion sur P=NP

    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

  26. #21
    Médiat

    Re : Réflexion sur P=NP

    Bonjour,
    Citation Envoyé par acx01b Voir le message
    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) ?
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  27. #22
    jobherzt

    Re : Réflexion sur P=NP

    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 !

  28. #23
    exciton

    Re : Réflexion sur P=NP

    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

  29. #24
    Noress

    Re : Réflexion sur P=NP

    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 ?

  30. Publicité
  31. #25
    Noress

    Re : Réflexion sur P=NP

    Citation Envoyé par Noress Voir le message
    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.

Discussions similaires

  1. Reflexion personnelle sur le Temps
    Par Rhadamantys dans le forum Physique
    Réponses: 12
    Dernier message: 01/09/2007, 15h09
  2. Réflexion sur le réchauffement climatique
    Par chris111 dans le forum Environnement, développement durable et écologie
    Réponses: 17
    Dernier message: 18/03/2007, 22h06
  3. Réflexion sur le placebo
    Par Démostène dans le forum Discussions scientifiques
    Réponses: 44
    Dernier message: 26/11/2006, 15h51
  4. Réflexion sur Préampli audio !
    Par gimmy dans le forum Électronique
    Réponses: 10
    Dernier message: 29/07/2004, 20h00