à propos de P=NP

[ilelogique]

Bonjour,
si j'ai bien compris, prouver que P=NP reviendrait à trouver un algorithme qui permettrait de résoudre en temps polynomial n'importe lequel des problèmes NP-complets (comme le voyageur de commerce par exemple).
Ma question est double et porte sur cet hypothétique algorithme :
1) Si on trouvait un énoncé équivalent au problème du voyageur de commerce ( VC : y a-t-il un chemin passant par n points donnés de longueur inférieur à k ?) qui se résoudrait en temps polynomial, alors me confirmez-vous bien qu'on aurait résolu P=NP ?

2) dans cette même optique, peut-on imaginer, si un tel algorithme existait (résoudre VC en temps polynomial), que celui-ci procède en un nombre fini d'étapes ? Je veux dire, par exemple, peut-on imaginer que, pour résoudre VC en un temps polynomial, l'algorithme commence par trouver un énoncé VC1 équivalent à VC qui se résout "plus rapidement", puis un énoncé VC2 équivalent à VC1 qui se résoudrait plus vite encore et cela jusque, mettons par exemple, VC6 (équivalent à VC5...) qui, lui, se résoudrait en temps polynomial ? Au fond, je crois, ma question peut aussi se formuler ainsi : peut-on imaginer par exemple une suite ordonnée de 6 mathématiciens M1, M2...M6 qui ne se connaissent pas mais ayant chacun un énoncé VC1, VC2...VC6 équivalent au précédent (VC1 <=>VC2 / VC2 <=> VC3 ... (oui je sais que l'équivalence est transitive...)et avec VC1=VC) dont les temps de résolution seraient ainsi t1 > t2>... >t6 (avec t6 polynomial) de sorte que (Mi ne connaissant que l'énoncé de Mi-1) aucun des mathématiciens ne puisse donner l'algorithme de VC en temps polynomial et que pourtant celui-ci existerait si seulement les 6 mathématiciens étaient réunis ???

En espérant m'être fait comprendre...

Merci.
-----

[obi76]

Bonjour,

peu importe la méthode ou l'algo pour le VC : tant que ce qu'il sort est toujours LE chemin le plus court (pas "un des" chemins le plus court).

[ilelogique]

En termes de décision, le VC est NP-complet dans sa version avec une réponse OUI/NON, d'où la variable k, mais cela dit ce n'est pas ma question, on peut remplacer VC par n'importe quel problème NP-complet dans ma question (sac à dos, SAT ou autre et qui attend une réponse oui ou non). Je demande juste si on peut envisager ce que j'ai dit (des étapes distinctes et finies de complexité décroissante)
merci

[ilelogique]

Par ailleurs (3e question) je ne vois pas quel algorithme polynomial permet de tester une solution proposée à VC

[A voir en vidéo sur Futura]

[Deedee81]

Salut,

1) Si on trouvait un énoncé équivalent au problème du voyageur de commerce ( VC : y a-t-il un chemin passant par n points donnés de longueur inférieur à k ?) qui se résoudrait en temps polynomial, alors me confirmez-vous bien qu'on aurait résolu P=NP ?

A condition que "équivalent" signifie NP-Complet alors oui.

2) dans cette même optique, peut-on imaginer, si un tel algorithme existait (résoudre VC en temps polynomial), que celui-ci procède en un nombre fini d'étapes ?

Forcément ! S'il faut un nombre infini d'étapes il ne risque pas d'être polynomial puisque le calcul ne se terminerait même jamais !!!!

La méthode que tu propose avec les VC1 etc.... j'ignore si ce serait vraiment efficace. Et si P!=NP (ce que pensent la majorité) ça me marcherait pas.

EDIT je viens de comprendre ce que tu viens de dire sur le nombre infini d'étapes. Non, tu n'aboutirais pas nécessairement au résultat en un nombre fini d'étapes. Ni même infini ! C'est assez évident.

Par ailleurs (3e question) je ne vois pas quel algorithme polynomial permet de tester une solution proposée à VC

Je ne le connais pas non plus mais il doit exister

[ilelogique]

merci pour votre réponse, mais ce n'est pas ma question, je ne demande pas si ce serait efficace mais bien si ça serait plausible, possible : peut-on envisager la situation que je dis avec les 6 mathématiciens qui ne se connaissent pas ? Dans le sens où chacun aurait un bout de l'algorithme (je sais bien que celui-ci est forcément fini) et que on aurait N=NP sans qu'aucun des mathématiciens puisse utiliser l'algorithme
merci

[pm42]

Globalement dire que quelque chose existe mais ne pas savoir l'expliciter ne serait pas nouveau en maths. Tu peux essayer de définir une base des fonctions continues de R dans R par exemple et plus rigolo, tu as les nombres Omega de Solovay qui sont parfaitement définis mais dont on ne peut connaitre aucun chiffre.

Voir https://fr.wikipedia.org/wiki/Oméga_de_Chaitin ou si tu es abonné : https://www.pourlascience.fr/sd/math...omega-4725.php

[Deedee81]

merci pour votre réponse, mais ce n'est pas ma question, je ne demande pas si ce serait efficace mais bien si ça serait plausible, possible : peut-on envisager la situation que je dis avec les 6 mathématiciens qui ne se connaissent pas ? Dans le sens où chacun aurait un bout de l'algorithme (je sais bien que celui-ci est forcément fini) et que on aurait N=NP sans qu'aucun des mathématiciens puisse utiliser l'algorithme
merci

Oui c'est possible (si c'était par hasard ce serait quand même invraisemblable). Découper une méthode un algo, pour ne pas le dévoler, c'est une technique connue (*)

Il existe des trucs bien plus extraordinaires. Par exemple, suppose que je trouve la démonstration que P != NP (à mon avis ils sont différents)
Je veux que tu le vérifies mais je ne veux pas te dévoiler ma démonstration car je ne l'ai pas encore publié. Et bien il existe une méthode qui te permet de vérifier sans connaitre ma démonstration !!!!
https://fr.wikipedia.org/wiki/Preuve...e_connaissance

C'est surtout utilisé en cryptographie l'idée : prouver que je connais un mot de passe mais sans donner ce mot de passe)

(*) et il existe même une méthode pour utiliser l'algorithme sans que les mathématiciens ne doivent dévoiler leur partie. J'ai lu la technique dans Pour La Science il y a quelques mois. La le but état d'améliorer les preuves d'examens à distance problématique bien actuelle)

[Deedee81]

On s'est croisé, et attention : ce que dit pm42 et ce que je dit n'est pas contradictoire.

pm42 parle de preuves d'existences sans expliciter un cas concret (c'est archi courant en math), on parle aussi de preuves non constructives.
Et moi je parlais de cas concret dont on prouve qu'on a trouvé ce cas mais sans le dévoiler.
(l'exemple que j'avais vu dans un article était basé sur la recherche des chemins hamiltoniens)

EDIT ça me fait penser aussi, lu dans l'article du Millenium : si on trouvait un algorithme P=NP celui-ci ne serait pas nécessairement utilisable un algo en x^100 par exemple serait polynomial mais totalement inutilisable, pire qu'un exponentiel en pratique.

[ilelogique]

merci, oui, ça commence à se rapprocher de ma question, et j'entends bien ce que vous dites, oui pm42 et preuves non constructives (il existe deux irrationnels qui l'un puissance l'autre donne un rationnel par exemple je crois) et oui Deedee81 je vais aussi suivre votre piste, merci.

Cela dit, dans ce que je demande, l'idée est que chaque partie de l'algorithme permette néanmoins un peu d'améliorer la vitesse à chaque fois, je vais essayer de mieux formuler ma question, de façon plus rigoureuse, sachant que ce que je demande est :
Selon vous, une telle chose est-elle envisageable, concevable, possible ? :

1) On suppose que P=NP et qu'il existe donc un algorithme A qui permet de résoudre en temps polynomial n'importe quel problème NP-complet.

2) A partir de l'algorithme A, je crée 6 algorithmes A1, A2,...A6 tels que chacun résolve un problème NP-complet (mettons VC) dans un temps t1 non polynomial (on peut bien sûr imaginer 4, 12 ou n'importe quel nombre entier d'algorithmes (c'est là que je parlais de finitude)

3) L'idée serait la suivante :

- Si on possède seulement un Ai alors on résout dans le temps t1, non polynomial, comme dit plus haut.

- Mais si on possède 2 algorithmes Ai ET Aj (i!=j) alors, en les "mélangeant", on obtiendrait un algorithme qui résoudrait (mettons VC) dans un temps t2, non polynomial mais avec t2<t1 (inégalité stricte)

- Si on possède 3 algorithmes Ai, Aj et Ak (i, j et k distincts) alors obtient un algorithme qui résout en un temps t3 non polynomial mais avec t3<t2

- idem, t4<t3 si on a 4 algorithmes et t5<t4 avec 5 algorithmes (t4 et t5 non polynomiaux)

- Enfin seulement si on a réuni les 6 algorithmes A1, A2... A6, alors on parvient à obtenir une résolution en t6<t5 avec t6 polynomial


Du coup on serait dans une situation où :

Plus un logicien spécialiste de la complexité algorithmique serait en possession d'un grand nombre d'Ai, plus il saurait résoudre rapidement VC (ou tout autre problème NP-complet) mais il ne saurait résoudre en temps polynomial QUE si il est en possession des 6 algorithmes.

Cela vous paraît-il possible ???

En suivant Deedee81 on pourrait aussi imaginer d'augmenter la suite de mes Ai en imaginant réduire encore la puissance du polynôme (si A1... A6 donnent t6 polynomial en x^100 alors A1... A7 donnerait t7 en x^50 etc....)

PS : Par ailleurs, au fait, comment appelle-t-on les problèmes dont même la vérification d'une solution de décision proposée n'est pas polynomiale ??? Y en a-t-il seulement ?

Merci !

[Médiat]

(il existe deux irrationnels qui l'un puissance l'autre donne un rationnel par exemple je crois)

Il existe une preuve non constructive en deux lignes, mais il existe aussi une preuve constructive

[Merlin95]

Globalement dire que quelque chose existe mais ne pas savoir l'expliciter ne serait pas nouveau en maths. Tu peux essayer de définir une base des fonctions continues de R dans R par exemple et plus rigolo, tu as les nombres Omega de Solovay qui sont parfaitement définis mais dont on ne peut connaitre aucun chiffre.

Voir https://fr.wikipedia.org/wiki/Oméga_de_Chaitin ou si tu es abonné : https://www.pourlascience.fr/sd/math...omega-4725.php

Pour Omega de Châtain je crois que ce qu'on peut dire c'est qu'au moins une décimale n'est pas calculable.

[ilelogique]

Bonjour, personne n'a de réponse à mes questions svp ?
Merci

[pm42]

Bonjour, personne n'a de réponse à mes questions svp ?

Là comme ça, au réveil, j'ai l'impression que ce que tu cherches ne marche pas. Déjà, tu parles de "mélanger" des algorithmes sans définir ce que tu entends par là. Dès lors, il est difficile d'être rigoureux et on ne peut pas faire des maths avec de vagues concepts interprétables à loisir.

[Médiat]

Comme pm42 (encore merci), je ne suis pa sûr de comprendre, mais si un algorithme fait passer d'un état (dont la résolution est NP-complète) à un autre état dont la résolution peut-être :

1) NP-complète, et on n'a rien gagné pour la solution de P=NP (autant partir de ce point)
2) Polynomiale, et le problème est résolu

Donc, sous réserve que j'ai compris la question, l'intérêt des algorithmes successifs est nul.

[Deedee81]

Salut,

J'avais mal compris le "mélange" au début, j'avais compris ça comme des algorithmes successifs de plus en plus efficaces en s'inspirant des précédents.
Et si on parle d'un vrai mélange au sens d'une soupe, sans précision je doute qu'on puisse répondre.

Pire que ça, utiliser (mélanger) plusieurs algos est irréalisable sauf gros chance (des trucs qui collent bien ensemble, on a une chance infime). Ou pire encore : on obtient quelque chose de moins efficace. C'est quelque chose de bien connu en cryptographie : utiliser deux algorithmes de crypto différents successivement en se disant "ça sera encore mieux crypté" hé bien... c'est une mauvaise idée. J'avais vu des exemples (il y a longtemps) où le résultat contenait des failles permettant aux cryptanalistes de casse le code.

Ici j'aurais tendance à dire la même chose. Les algos sont optimisés tout azimuth : mathématiquement, informatiquement (programmation), numériquement... Les mélanger c'est surtout risquer d'avoir un bousin hyper lourd et inefficace.

Une exception est quand chaque algo opère dans des domaines différents. Par exemple, des algorithmes de tri par insertion sont très efficaces pour N très petit (en partie à cause de leur simplicité) mais plus loin un quick sort ou un heap sort devient incontournable. On pourrait avoir un algo assez efficace pour un problème NP-Complet pour N petit et un autre pour N grand. Mais ce n'est évidemment pas ça "mélanger" des algorithmes et ça ne risque pas de transformer des algo exponentiels en algos polynomiaux.

De plus je crois que ilelogique comment une grosse erreur de logique (un comble ). De ce que je lit ci-dessus j'ai l'impression qu'il pense qu'avec des algos dont le temps t de résolution diminue on passe d'une solution exponentielle à polynomiale. Mais c'est faux. Pour un problème donné (classe P) il existe des algorithmes exponentiels rapides prenant un temps t1 (pour N donné) et des algos polynomiaux lent prenant un temps t2 avec t2 > t1.

Non, non, non, avoir un algorithme polynomial ne veut pas dire nécessairement rapide. C'est un peu plus compliqué que ça. Il me semblait avoir été clair dans le message 9 mais il est probable qu'on se soit croisé.

Polynomial ou exponentiel ne concerne pas le temps de résolution d'un problème donné mais le comportement de l'algorithme lorsque la taille du problème augmente. Si on avait un algo exponentiel efficace pour N > 1000000 dans le voyageur de commerce, ma foi, les informaticiens n'en auraient rien à faire d'un algo polynomial (en fait on en a des efficaces mais des approchés "presque justes", mais c'est un autre problème).

Ce problème P=NP est en petite partie un soucis pratique et en grande partie un soucis mathématique.

[Deedee81]

Ce problème P=NP est en petite partie un soucis pratique et en grande partie un soucis mathématique.

(jusqu'au jour où on aura des calculateurs avec quelques millions de q-bits là ce sera TRES pratique )

[pm42]

jusqu'au jour où on aura des calculateurs avec quelques millions de q-bits

Rien que ça ? Je ne sais pas si c'est vraiment possible vu les problèmes actuels ni utile : quel problème nécessiterait des millions de qbits ?
Ceci dit, si c'est comme le reste de l'informatique, on y arrivera et quand on y sera, on se dira qu'avec quelques milliards, on pourrait encore faire plus

[Deedee81]

Rien que ça ? Je ne sais pas si c'est vraiment possible vu les problèmes actuels ni utile : quel problème nécessiterait des millions de qbits ?
Ceci dit, si c'est comme le reste de l'informatique, on y arrivera et quand on y sera, on se dira qu'avec quelques milliards, on pourrait encore faire plus

Le chiffre était un peu au pif. Pour signaler un cas où l'approche polynomiale (mais le problème est différent de P=NP, ne pas surinterpréter) pouvait donner des cheveux gris. Mais d'un autre coté, l'élaboration des algorithmes dit post-quantiques est en plein boum.
https://fr.wikipedia.org/wiki/Crypto...post-quantique

Bon, là je dérive un peu (pour peu qu'il y ait encore quelque chose à dire sur cet étrange et fantasmatique mélange d'algorithmes). Désolé.

[pm42]

Le chiffre était un peu au pif.

Les évaluations actuelles sont de quelques milliers de qbits pour cracker du RSA ou le codage du bitcoin.
Et comme la puissance est une exponentielle du nombre de qbits, de millions arriveraient à simuler l'ensemble de l'Univers ou un truc comme ça.

[Deedee81]

Les évaluations actuelles sont de quelques milliers de qbits pour cracker du RSA ou le codage du bitcoin.

D'accord, merci de la précisions (numérique).

Et comme la puissance est une exponentielle du nombre de qbits, de millions arriveraient à simuler l'ensemble de l'Univers ou un truc comme ça.

Effectivement, ceci dit je doute que ce soit aussi simple, mais bon, je peux me tromper. L'avenir (sans doute assez proche) nous le dira.

[ilelogique]

Bonjour et merci pour vos nombreuses réponses.
D'une part je ne vois pas où j'ai fait une faute de logique (merci de me l'indiquer svp ?), car je ne crois pas ignorer que ce n'est pas parce que le temps diminue qu'on parvient forcément à P et je sais aussi qu'on peut avoir un temps de calcul plus bref en exponentielle qu'en polynôme sauf, bien sûr, à partir d'un certain stade sur les entrées me semble-t-il. Donc, oui, polynomial ne veut pas dire rapide. Et enfin je sais très bien qu'on ne fait pas de maths avec des "vagues concepts interprétables à loisir", mais pour le coup je ne suis pas certain de faire vraiment des maths ici avec ma question...

Ensuite à propos de mon "mélange" (que j'ai mis entre guillemets exprès) je conviens qu'il y a du flou, je vais donc tâcher de re-préciser ma question :

Tout d'abord je voudrais insister sur le sens de ma question, je ne cherche ni formule ni algorithme précis (donc pas vraiment besoin de rigueur) mais surtout à savoir si ce que je demande est logiquement plausible, possible, envisageable (et là bien sûr il s'agit de rigueur...)

Ensuite je m'aperçois que ce que j'ai appelé algorithmes A1...A6, n'en sont pas forcément, chaque Ai pourrait peut-être être vu comme "un ensemble d'informations précises et non ambiguës permettant de tirer un algorithme", l'idée étant bien la même (et j'ajoute A7... An pour plaire à Deedee81 .... ce qui à mon avis ne change rien si la réponse à ma question est positive, du fait qu'on pourra "coupler, unir" les Ai)

Est-il possible d'imaginer un ensemble E = {A1, A2... An}, où chaque Ai est un "ensemble précis d'informations permettant d'obtenir un algorithme", de sorte que :
Pour i allant de 1 à n, à n'importe quel sous-ensemble de E à i éléments on puisse associer un même temps ti (t1 pour 1 ensemble d'informations, t2 pour 2 ensembles d'informations, tn avec tous les Ai) de sorte que t1>t2>....>tn et tn polynomial en degré 2 (soyons fous pour Deedee81...) et où pour tout i chaque sous ensemble de E à i éléments permette de donner un algorithme résolvant VC (où tout au problème NP-complet) en un temps ti (qui ne dépendrait bien sûr que des entrées du problème (comme le nombre de villes et l'entier k mentionné plus haut pour VC)) ?

En gros : plus on aurait d'Ai plus on résoudrait vite VC, et on serait (pourquoi pas) en x² avec tout E.
je pensais par exemple à ce que chaque Ai contienne une fonction fi et que la composée fiofj (composition des fonctions) permette d'"accélérer" l'algorithme...

Il va de soi, je m'en rends compte, que ma question pourrait porter sur la complexité algorithmique de n'importe quel problème (NP-complet ou pas) (plus on a d'ensembles d'informations plus on peut déduire un algorithme rapide) puisque, si la réponse était positive je pourrais alors l'appliquer notamment à la question p=?NP

Je dois enfin avouer que l'argument de Deedee81 me chagrine un peu quand il dit que souvent si on "mélange" des algorithmes on risque d'avoir moins d'efficacité... mais est-ce certain ???
voilà
merci


PS : je re-demande mon autre question (simple curiosité du coup) : comment appelle-t-on les problèmes dont même la vérification d'une solution de décision proposée n'est pas polynomiale ??? Y en a-t-il seulement ?

[ilelogique]

Pour répondre partiellement à Médiat, je suis bien conscient que dans ce que je propose il existerait un i à partir duquel on aurait déjà P=NP (sans forcément d'efficacité calculatoire réelle)
Cependant ma question repose moins sur l'intérêt de la question P=?NP (certes passionnante sur le plan mathématique) que sur l'efficacité calculatoire du-dit algorithme de P=NP et surtout cette répartition progressive en termes de vitesse des algorithmes

[Deedee81]

Salut,

D'une part je ne vois pas où j'ai fait une faute de logique (merci de me l'indiquer svp ?), car je ne crois pas ignorer que ce n'est pas parce que le temps diminue qu'on parvient forcément à P et je sais aussi qu'on peut avoir un temps de calcul plus bref en exponentielle qu'en polynôme sauf, bien sûr, à partir d'un certain stade sur les entrées me semble-t-il. Donc, oui, polynomial ne veut pas dire rapide. Et enfin je sais très bien qu'on ne fait pas de maths avec des "vagues concepts interprétables à loisir", mais pour le coup je ne suis pas certain de faire vraiment des maths ici avec ma question...

Alors si tu avais bien compris, excuse-moi. Mais le fait est que tes explications n'étaient pas du tout claire.

Pour le reste ce n'est toujours pas clair (enfin, en tout cas pour moi), c'est ,quoi le genre "d'informations permettant de tirer un algorithme" ???? (le reste est encore plus brumeux)

Pour répondre partiellement à Médiat, je suis bien conscient que dans ce que je propose il existerait un i à partir duquel on aurait déjà P=NP

???? Le statut P=NP ne dépend pas de i, il ne dépend même pas des algorithmes mais seulement du problème considéré. Tu peux avoir uniquement des algo exponentiels et avoir P=NP (ça veut juste dire qu'on n'a pas encore trouvé d'algorithme polynomial mais qu'il doit en exister un). Je suppose que tu as voulu répondre "je suis bien conscient que dans ce que je propose il existerait un i à partir duquel on aurait déjà un algorithmes polynomial" ?

Perso je pense que P != NP, qu'il n'existe pas d'algorithmes polynomial. Le plus clair est le problème NP-Complet 3-sat.
https://fr.wikipedia.org/wiki/Probl%C3%A8me_3-SAT

Il suffit de jouer un peu avec pour se convaincre qu'il n'existe pas d'autre approche qu'exhaustive/combinatoire. Evidemment, ce n'est pas une preuve, mais c'est suffisamment convaincant pour être à peu près sûr que P != NP.

[ilelogique]

c'est ,quoi le genre "d'informations permettant de tirer un algorithme" ???? (le reste est encore plus brumeux)

On y vient justement c'est bien pour ça que ma question est de la forme "Pensez-vous qu'il soit envisageable, trouvez-vous cela plausible ?" etc. Je n'ai pas forcément besoin de savoir exactement ce que contiendraient mes Ai mais surtout de savoir si on peut imaginer qu'ils puissent exister !!

Je suppose que tu as voulu répondre "je suis bien conscient que dans ce que je propose il existerait un i à partir duquel on aurait déjà un algorithmes polynomial"

Oui oui tout à fait, mais cela impliquerait bien (si on part d'un problème NP-complet) qu'avec seulement i (et non pas n) éléments de E on aurait déjà la preuve de N=NP

Pour le 3-SAT oui, étonnant que 2 SAT soit P pourtant...

Enfin, de façon fictionnelle, j'ai "besoin" que P=NP (même si personne n'y croit ce n'est pas grave, j'ai bien le droit de l'envisager tant que ce n'est pas invalidé...) et du coup je me demande si les Ai dont je parle pourraient exister ???

Merci

PS : que pensez-vous de mon précédent PS SVP ?

[Deedee81]

On y vient justement c'est bien pour ça que ma question est de la forme "Pensez-vous qu'il soit envisageable, trouvez-vous cela plausible ?" etc. Je n'ai pas forcément besoin de savoir exactement ce que contiendraient mes Ai mais surtout de savoir si on peut imaginer qu'ils puissent exister !!

Sans comprendre de quoi tu parles, la question va être très difficile à répondre !!!!! On ne sait même pas ce qui pourrait bien être plausible.
(parce que là ça ressemble à "j'ai une idée : en faisant des trucs et des machins on pourrait résoudre le problème. Pensez-vous que mon idée soit plausible" !!!!!)

Il faut absolument rendre ton explication plus claire. Revenons à ma question à laquelle tu n'as pas répondu. Tu parles d'informations : quel genre d'information exactement ????
(tu n'as pas employé ce mot au hasard.... sinon on est vraiment mal barré.... alors explique-le s'il te plaît)

P.S. non, il y en a quelques uns qui pensent que peut-être bien que P=NP

[gg0]

Je plussoie :

"je ne cherche ni formule ni algorithme précis (donc pas vraiment besoin de rigueur) mais surtout à savoir si ce que je demande est logiquement plausible, possible, envisageable (et là bien sûr il s'agit de rigueur...)"
Manifestement, tu vis dans le rêve !! Ce n'est pas seulement pour des choses précises qu'il faut de la rigueur, c'est aussi dans sa pensée. Quand on manipule les mots en dehors de leur signification courante, qu'on est obligé de changer d'explication à chaque demande de précision, c'est qu'on ne sait pas vraiment de quoi on parle.

Donc pour savoir si quelque chose dont tu veux parler est "logiquement plausible, possible, envisageable", il faut que toi, tu fasses preuve de rigueur. Que tu cherches vraiment quelle est ton idée (s'il y en a une), et comment on peut l'exprimer. C'est souvent dans cette étape que les gens qui réfléchissent vraiment (pas en mettant 20 lignes floues sur un forum, dans leur tête) s'aperçoivent que ce qu'ils prenaient pour une idée n'a pas de corps, perd son sens.

Et comme tu es coutumier du fait, commence par rédiger, pour toi, un texte parfaitement précis, lisible par tout le monde. N'attends pas qu'on donne ici un sens à tes rêveries.

[gg0]

Des demandes contradictoires :
"je ne cherche ni formule ni algorithme précis.."
"ma question repose moins sur l'intérêt de la question P=?NP (certes passionnante sur le plan mathématique) que sur l'efficacité calculatoire du-dit algorithme de P=NP (sic) et surtout cette répartition progressive en termes de vitesse des algorithmes "

C'est vraiment incohérent !!

[Deedee81]

C'est vraiment incohérent !!

Bievenue au club

J'espère déjà de savoir ce qu'il veut dire par le premier mot (information), on verra la suite après. Mais on n'est pas sorti de l'auberge.

[ilelogique]

Bon, déjà je remets mon "PS" car personne n'a répondu et j'espère que c'est clair :
comment appelle-t-on les problèmes dont même la vérification d'une solution de décision proposée n'est pas polynomiale ? Y en a-t-il seulement ?

Ensuite Deedee81, j'entends par information le sens usuel du dico (renseignements, indications) mais que celles-ci soient bien sûr non équivoques et précises (pourquoi pas codables si vous le voulez), je vais essayer de donner un exemple plus bas.
je passerai sur les leçons moralisatrices de ggp qui enfonce des portes ouvertes selon moi et je ne développerai car je vise seulement ma question (non, ce que j'ai dit n'est pas incohérent ni contradictoire, relisez svp), je sais que les maths et la pensée doivent être rigoureuses mais ça n'empêche pas la poésie...

Alors pour simplifier je vais commencer par virer la question de P=NP et donner un exemple, je ne serai pas 100% rigoureux car je ne vais pas ici décrire des algorithmes dont chacun sait bien qu'ils existent :
Je considère le problème (qui n'est pas à réponse oui/non ici) consistant par exemple à trouver l'entier le plus petit dans une liste de n entiers et j'admets (j'espère que je le peux !) qu'il existe au moins 3 algorithmes résolvant ce problème en des temps t1>t2<t3
soit A1 l'ensemble d'informations suivant : {1) un algorithme qui sépare les n entiers en 3 paquets de cardinal le plus proche possible puis qui trie de façon brutale le premier paquet (je prends le premier, je le compare au second et tant qu'il est plus petit je passe au suivant, dès que je trouve plus petit je le prends, etc. (désolé pour mon manque de formalisme ici mais je pense pouvoir supposer que chacun me suit non ???), puis idem avec le 2e paquet puis le 3e paquet et enfin il détermine le plus petit entier des 3 entiers sortis. 2) la première moitié d'un algorithme résolvant en t2. 3) la première moitié d'un autre algorithme résolvant en t2.4) le premier tiers d'un algorithme résolvant en t3. 5) la date de naissance de Napoléon (pour Deedee81...) et 6) un tuto expliquant comment repérer si on a le début le milieu ou la fin d'un algorithme et comment concaténer des algorithmes... }
puis de même A2 = {1) le même algorithme que dans 1) de A1 sauf qu'il commence par le 2e paquet, puis le troisième puis le premier.2) la deuxième partie de l'algorithme du 2) de A1. 3) le même que 3) de A1. 4) le 2e tiers de l'algo de 4) de A1. 5) la taille qu'avait Bill Gates à 27 ans exprimée en base 7 et 6) le même tuto que dans 6) de A1}
et enfin A3 = {1) le même que 1) de A1 sauf qu'il commence par le 3e paquet. 2) la 2e partie de 2) de A1. 3) la 2e partie de l'algo 3) de A1. 4) le 3e tiers de l'algo en t3, 5) l'heure qu'il était quand Elvis est mort et 6) le tuto}

il me semble qu'on est alors dans le cas suivant :
- Si on ne possède que A1 ou que A2 ou que A3 alors on peut seulement trouver le plus petit entier en un temps t1 (qui dépend de n évidemment)
- Si on a 2 parmi les trois A (A1 et A2 ou A2 et A3 ou A1 et A3) on peut résoudre en t2
- Si on a A1, A2 et A3 alors on peut résoudre en t3

Aussi (dites moi si je me trompe ?) je pense avoir exhibé un exemple d'un ensemble E = {A1, A2, ... An} (avec n égal 3) tel qu'on résout un problème p en temps ti si on possède i éléments de E et avec t1>t2...>tn

ma question revient à demander s'il peut sembler raisonnable, en supposant que P=NP et qu'on ait un algorithme pour résoudre un problème NP-complet en temps polynomial (et je répète, ici pas forcément besoin de formalisme...) de faire une chose semblable pour celui-ci et avec tn au moins qui est polynomial ??

En espérant que mon exemple ait clarifié ce que je demande ?

Merci