Discussion:NP (complexité)

Création en ébauche

Bonjour,

hum ça faisait pas mal de temps que je me disais qu'il faudrait que cette page existe en tant que tel, et pas seulement en creux dans problème P=NP et problème NP-complet, donc la voilà, mais je n'ai pas le temps de vraiment mettre des choses dessus. J'ai mis le nécessaire pour que ce ne soit pas ridicule.

Cordialement, --Roll-Morton (d) 13 mars 2013 à 14:01 (CET)

Suppression non justifiée de mon amélioration

 Benoît Prieur : a supprimé ma modification de l'introduction sous le prétexte qu'elle était bizarrement exprimée. Est-ce qu'exprimer un concept pour que tout le monde le comprenne est faire preuve de bizarrerie. Cette façon bizarre est néanmoins celle que j'ai utilisée pour introduire le concept à mes étudiants (voir aussi Nicolas Hermann et Pierre Lescanne, Est-ce que P = NP ? Les Dossiers de La Recherche, 20:64–68, août-octobre 2005). Ceci dit, vous êtes-vous rendu compte de la formulation complètement absconse de votre introduction ? Un lecteur moyen qui veut savoir ce qu'est la complexité NP et qui a un bagage scientifique limité n'a aucune chance de comprendre ce que ça veut dire et rejoindra les critiques qui disent que les articles de mathématiques de Wikipédia sont incompréhensibles. Donc pour l'instant je rétablis ma définition et j'attends la discussion sur cette page. --Pierre de Lyon (discuter) 25 novembre 2015 à 10:06 (CET)

Bonjour Pierre de Lyon,

La première version incluait un "le vérification" qui fait que je n'ai pas compris la phrase ou du moins que j'ai eu quelques doutes à son sujet. Après correction et relecture c'est effectivement plus claire : elle constitue de la bonne vulgarisation (autant que je connaisse le sujet).

Cordialement, --Benoît Prieur (discuter) 25 novembre 2015 à 10:53 (CET)

NP ne veut pas dire Non Polynomial

Suis-je le seul à avoir cru au départ que NP voulait dire Non Polynomial ? Ou y a-t-il un piège que nous devrions signaler en bons pédagogues? --Pierre de Lyon (discuter) 25 novembre 2015 à 15:08 (CET)

Oui le sigle est un peu malheureux, on a tendance à penser « non polynomial », alors que NP contient P, que des problèmes clairement non polynomiaux n'y sont pas (ceux de EXPTIME par exemple), et que l'on ne sait pas si en effet P est différent de NP. Je ne sais pas si un avertissement doit figurer dans l'article. Peut-être. Il faudrait voir si c'est une remarque classique dans les bouquins. En tout cas pour répondre vraiment à la question : oui j'ai vaguement pensé ça au début. --Roll-Morton (discuter) 25 novembre 2015 à 17:45 (CET)