Vulgarisation problème NP

[invite0b2ae292]

Bonjour !
je ne connais presque rien à la programmation et aux maths, mais j'ai lu des choses sur ces histoires de problèmes NP :
notamment j'ai lu que composer un emploi du temps scolaire qui fonctionne, avec les contraintes multiples de disponibilités de profs, d'élèves, de salles... était un exemple de problème NP, et de ce fait ne pouvait être composé par un programme informatique à lui tout seul.
J'ai l'impression qu'il y a toute la documentation qu'on peut vouloir sur le sujet sur internet, mais je n'arrive pas à en trouver de niveau assez bas pour moi.
Par exemple, sur les emplois du temps, j'ai trouvé cette discussion, où le nommé Sriliam dit cela

lorsque l'on retire une petite quantité de données dans un problème et que l'on obtient le même ordre de grandeur, c'est que l'on est en face d'un problème np-complet. np signifie non polynomial et complet, bah la complétude, comme dans R, il est complet cet ensemble. Dans un ouvert, vous aurrez toujours une infinité d'élément, quelque soit le epsilon, tout petit, d'écart entre les 2 bornes !
C'est dur à montrer ça, au cas par cas, c'est pourquoi je préfère retirer une petite quantité de données initiales ( nb prof, nb salle, nb classe) et constater que la complexité ne change pas. C'est dur à montrer ça, au cas par cas, c'est pourquoi je préfère retirer une petite quantité de données initiales ( nb prof, nb salle, nb classe) et constater que la complexité ne change pas...

Et bien sûr, je n'y comprends rien.
Je comprends vaguement que c'est une histoire de contraintes multiples, mais il y a plein de problèmes qui ont des contraintes multiples, et tous ne sont pas NP, j'imagine ?...
C'est possible d'expliquer avec des mots simples pourquoi un problème est NP, comment on reconnaît un problème NP ?
Merci en tout cas de vous être penché sur mon message.
-----

[JPL]

J'ai déplacé la question en math car ce forum me semble plus adapté.

[invite251213]

En fait, les explications que tu as citées dans le message que tu cite me semblent douteuses, à première vue...

Un problème NP-complet est assez simple à comprendre au final : c'est un problème dont on peut vérifier facilement qu'une solution proposée est correcte, mais pour lequel le calcul d'une solution est souvent très long.

Explications : imagine que tu aies un problème à résoudre, via un algorithme. Cet algorithme va devoir manipuler une certaine quantité de données fournies en entrée, et va fournir une réponse en sortie. Pour fournir cette réponse, notre algorithme va effectuer une suite de manipulations élémentaires sur les données d'entrée (et aussi sur d'autres données temporaires, mais passons). Ces manipulations sont souvent des opérations du style comparaisons, additions, et autres opérations arithmétiques.

Il semble évident que si on augmente le nombre de données fournies en entrées, la quantité de calcul peut augmenter (ce n'est pas une obligation, et quelques exceptions existent). Pour éviter les surprises, les informaticiens aiment quantifier le nombre d'opérations effectuées par un algorithme en fonction de la quantité de donnée fournies en entrée. Cela leur permet de savoir si leur algorithme va fonctionner correctement sur de grandes données, ou si l'ordinateur va rendre l’âme avant de fournir une solution. Ils calculent ce qu'on appelle la complexité de leur algorithme. Cela permet ainsi de dire des choses du style : si j'ai n données en entrée, mon algorithme effectuera un nombre constant d'opérations, ou quelque chose de proportionnel à n, ou proportionnel à ln (n), ou n(ln n), etc. Cette complexité n'est rien d'autre qu'une fonction de la taille des entrée qui fournit une approximation du nombre d'opérations effectuée par l'algorithme. Dit plus mathématiquement, Complexité d'un algo = f ( n ) , avec n la quantité des donnes fournies en entrée.

Un problème NP-complet est un problème pour lequel le plus efficace et le mieux conçu des algorithme peut vérifier si une solution est correcte assez rapidement. Par assez rapidement, on veut dire que la complexité de l'algorithme sera un polynôme. Par exemple, si tu as x entrée, ton algorithme fera ^{x^2} + 5x + 4 opérations. Ce genre d'algorithme est assez correct : en règle générale, un ordinateur normal ne met pas 5 ans pour fournir un résultat en exécutant un programme se basant sur un tel algorithme.

Donc, les problème NP-complet sont résolubles rapidement quand on veut vérifier une solution. Le seul truc, c'est le calcul de cette solution. Et là, c'est autre chose : généralement, le calcul de cette solution est très lent : il peut devenir impossible en pratique, même avec un ordinateur sur-puissant ! La complexité du calcul (et non de la vérification) peut ainsi devenir exponentielle. Traduction : tu mets 50 ans à trouver une solution, mais tu peux au moins vérifier que celle-ci est correcte rapidement...

Du moins, c'est ce qu'on remarque en pratique : on ne sait pas si on peut faire mieux théoriquement. Si ça se trouve, on peut trouver des algorithmes rapides pour résoudre des problèmes NP-complet. En gros, on n'a jamais réussi à prouver que cette lenteur du calcul de solution d'un problème NP-complet était une fatalité.

C'est possible d'expliquer avec des mots simples pourquoi un problème est NP, comment on reconnaît un problème NP ?
Merci en tout cas de vous être penché sur mon message.

Le pourquoi un problème est NP, aucune idée. Le comment reconnaitre de tels problèmes, et bien à mon avis, à moins de faire des démonstrations mathématiques complexes, tu ne peux pas le savoir "facilement".

[JPL]

J'ajoute que la question de savoir si P≠NP ou P=NP n'est pas résolue. Autrement dit il n'est pas exclu (même si pour le moment on ne voit pas comment) que tout problème NP puisse être ramené à un algorithme polynomial, mais si te le démontres tu gagneras 1 million de dollars.

Tu peux regarder http://fr.wikipedia.org/wiki/Probl%C3%A8me_P_%3D_NP et l'article de l'excellent Jean-Paul Delahaye http://interstices.info/jcms/c_21832...ion-de-dollars.

[A voir en vidéo sur Futura]

[invite0b2ae292]

Merci beaucoup pour vos réponses, et pour les liens.

à moins de faire des démonstrations mathématiques complexes, tu ne peux pas le savoir "facilement".

Bon, je m’en doutais un peu. Rien que l’appellation, "Non Polynomial", vu mon niveau en maths, ce genre d’histoires me passe largement au-dessus de la tête. ("polynôme", jusque là, ça m’évoquait seulement le nom d’une ligne de bus qui passe près de chez moi, alors … Mais grâce à l'explication de mewtow, j'entrevois un peu ce que ça signifie :

la complexité de l'algorithme sera un polynôme. Par exemple, si tu as x en entrée, ton algorithme fera x^2 + 5x + 4 opérations

c'est un problème dont on peut vérifier facilement qu'une solution proposée est correcte, mais pour lequel le calcul d'une solution est souvent très long.

Je ne suis pas sûre de comprendre.
Par exemple, si je reprends l’exemple des emplois du temps, c’est facile de vérifier qu’un emploi du temps ne comporte pas de doublons de salles, ou de profs pour la même heure, ou de vérifier que des élèves n’ont pas quatre heures de maths à la suite. On peut programmer un ordinateur pour qu’il recherche tous les doublons et les incohérences de ce type, ce qui sera plus pratique que de vérifier tout ça à la main.
Par contre l’ordinateur mettra beaucoup de temps à concocter un emploi du temps cohérent (et "parfait") à partir des contraintes qu’on lui impose, c’est ça ?

Après, je vois vaguement ce que veut dire exponentiel (ça m’évoque le conte de l’inventeur du jeu d’échecs avec les grains de blés sur chaque case.).
Je vois aussi que les articles sur les problèmes NP parlent de graphes.
Cela me fait penser aux arbres qu'on fait en probabilités, par exemple. Chaque fois qu'on rajoute des branches au bout de l'arbre, on multiplie par toutes les branches précédentes, ce qui peut vite donner un nombre considérable. Est-ce que le problème vient un peu de là ?